java 实现排序算法之「冒泡排序」

• 重复执行

直到只剩一个元素，那么这个元素一定是最小元素，排序结束。显然，进行了 n-1 次排序。

上述过程，每次排序(即每轮排序)都会有一个元素从某个位置慢慢“浮动”到最终所属的位置,就像气泡总会浮动到水的最顶端。在冒泡排序中，每一轮排序都会有一个元素(气泡)替换到本次排序的最后一个位置(水的最顶端)，注意，是本次排序的最后一个位置(第一轮，则为 n；第二轮，则为 n-1；第三轮，则为 n-2 ~~~ )。

因为，排序的过程像是冒泡一样，则称为“冒泡排序”。如下为冒泡排序示意图(来自维基百科)

代码实现

设要给数组 arr[] 排序，它有 n 个元素。

public static void bubbleSort(int[] arr) {
    int temp = 0;
    for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
        for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

算法优化

假如有一组数据为：1,2,3,4,5,6,7,8,9,0。 如果用上面的方法实现排序会有什么情况，当然，实现排序肯定没有问题。但是，这组数据的前面一大部分已经是有序的了，如果还是用上面的代码会使效率降低很多(数据比较大的情况下)。所以，将代码进行优化。

public static void bubbleSort(int[] arr) {
    int temp = 0;
    boolean swap;
    for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
        swap=false;
        for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swap=true;
            }
        }
        if (swap==false){
            break;
        }
    }
}

在实际使用过程中，由于在大量数据的情况下几乎不使用冒泡排序，而使用小数据的时候增加的布尔变量反而会造成额外的开销。通常，冒泡排序就使用前一种就行了。

算法复杂度

• 时间复杂度

当最好的情况，也就是要排序的表本身就是有序的，那么我们比较次数，根据最后改进的代码，可以推断出就是n-1次的比较，没有数据交换，时间复杂度为O(n)。当最坏的情况，即待排序表是逆序的况，此时需要比较

次，并作等数量级的记录移动。因此，总的时间复杂度为O(n^2)。

• 空间复杂度

由以上算法步骤分析，可轻易得知冒泡排序的空间复杂度为 O(n), 需要辅助空间 O(1)

算法稳定性

容易看出，在相邻元素相等时，我们并不需要交换它们的位置，所以，冒泡排序是稳定排序。

算法适用场景

在算法优化中提到过，实际使用过程中，在大量数据的情况下几乎不适用冒泡排序。冒泡排序思路简单，代码简单，特别适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。

ikook
2017.03.21

---