排序算法之冒泡排序

概述

冒泡排序是一种简单的排序算法. 它重复的走过要排序的数列, 每次比较相邻的两个元素, 若它们的顺序错误就把他们进行交换, 如此循环进行, 直到冒泡到最后一个元素或本次比较不需要进行冒泡 就结束.

因为元素就像一个一个向上冒, 故而叫做冒泡算法, 个人理解.

冒泡排序的执行步骤如下(从小到大):

1. 从第一个元素开始, 向后依次比较 相邻元素的大小. 若前一个大, 则交换
2. 做到最后一位时, 最后的元素是最大的数
3. 最后一个元素已经比较完毕, 将其从比较序列中排除, 重复以上步骤.
4. 重复以上步骤, 知道没有元素需要交换或冒泡完毕

其时间空间复杂度如下:

不难理解, 直接上代码了.

Java代码实现

/**
 * 冒泡排序实现数组排序, 从小到达顺序
 * 
 * @param arr
 */
public static void bubbleSort(int[] arr) {
    /* 
     * 1. 遍历数组, 将左侧>右侧的元素交换
     * 2. 此时最大元素冒泡到数组末尾
     * 3. 将已经排序的元素去除, 重复步骤1-2
     */
    // i从后向前, 即将最大的冒泡到最后, 则不再理会这一元素
    for (int i = arr.length; i > 0; i--) {
        // 标志位, 判断是否进行了冒泡操作
        boolean flag = false;
        // 用于冒泡循环
        for (int j = 0; j < i - 1; j++) {
            // 若左侧元素大, 则进行交换
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                flag = true;
            }
        }
        // 若没有进行冒泡操作, 表示已经排序完成, 退出
        if (!flag) {
            break;
        }
    }
}