排序算法思路之冒泡：java、python代码实现

冒泡排序(Bubble Sort)

冒泡排序的核心部分是双重嵌套循环，持续比较相邻元素，大的挪到后面，因此大的会逐步往后挪，故称之为冒泡。

算法思路

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

图片源自Visualgo

实现

Java

public class BubbleSort {

    public static void main(String[] args) {
        int[] unsortedArray = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
        bubbleSort(unsortedArray);
        System.out.println("After sorted: ");
        for (int number : unsortedArray) {
            System.out.print(" " + number);
        }

    }

    private static void bubbleSort(int[] array) {
        if (array == null || array.length == 0) { // 非法检查
            return;
        }

        int i, temp, len = array.length;
        boolean changed;
        
        do {
            changed = false;
            len -= 1;
            for (i = 0; i < len; i++) {
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    changed = true;
                }
            }
        } while (changed);
    }
}


复制代码

Python

#!/usr/bin/env python
# coding=utf-8


def bubble_sort(arrayList):
    length = len(arrayList)

    for i in range(length - 1):
        count = 0

        for j in range(length - 1 - i):
            if (arrayList[j] > arrayList[j + 1]):
                arrayList[j], arrayList[j + 1] = arrayList[j + 1], arrayList[j]
                count += 1

        if count == 0:
            break


if __name__ == "__main__":
    arrayList = [6, 5, 3, 1, 8, 7, 2, 4]
    print("orgin array list: {0}".format(arrayList))
    bubble_sort(arrayList)
    print("after sorted list: {0}".format(arrayList))
复制代码

时间复杂度和空间复杂度

最好情况下：正序有序，则只需要比较n次。故为 O(n)

最坏情况下：逆序有序，则需要比较 (n-1)+(n-2)+……+1，故为 O(n^2)

因为需要一个临时变量来交换元素位置，(另外遍历序列时自然少不了用一个变量来做索引)，所以其空间复杂度为 O(1)

稳定性

排序过程中只交换相邻两个元素的位置。因此，当两个数相等时，是没必要交换两个数的位置的。所以它们的相对位置并没有改变，冒泡排序算法是稳定的。

总结

如果有 n 个数进行排序，只需将 n - 1 个数归位，也就是说要进行 n - 1 趟操作。而“每一趟”都需要从第 1 位开始进行相邻两个数的比较，将较小的一个数放在后面，比较完毕后向后挪一位继续比较下面相邻数的大小，重复此步骤，直到最后一个尚未归位的数，已经归位的数则无需再进行比较。

冒泡排序的核心部分是双重嵌套循环，不难看出冒泡排序的时间复杂度是 O(n^2)。这是一个非常高的时间复杂度。所以说冒泡排序除了它迷人的名字之外，似乎没有什么值得推荐的