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

冒泡排序（Bubble Sort）

冒泡排序的核心部分是一个双层嵌套循环，不断比较相邻元素，将较大的元素向后移动，这样大的元素逐渐变大向后移动，这就是为什么它们被称为泡沫。

算法思想

1. 比较相邻元素。如果第一个大于第二个，则替换两者。完成这一步后，最后一个元素将是最大的数字，必须比较这对数字

图片来自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))
复制代码

时间复杂度和空间复杂度

最好的情况：正序时间。因此，这是 O(n)

最坏的情况是：(n-1)+(n-2)+……+1 必须以相反的顺序进行比较，所以 O(n^ 2)

由于需要一个临时变量来交换元素位置（另外遍历序列时自然会使用变量作为索引），因此其空间复杂度为O(1)

稳定性

排序时仅交换两个相邻元素的位置。因此，如果两个数相等，则无需交换两个数的位置。因此，它们的相对位置没有改变，冒泡排序算法是稳定的。

总结

如果需要对n个数字进行排序，只需要返回n - 1，即。而“每趟”则需要从位置1开始比较两个相邻的数字，将较小的数字移到后面，完成比较后，再向后移动一个位置继续比较下面相邻数字的大小，重复该步骤，直到最后一个号码，尚未被替换，，替换后的号码不需要比较。

气泡排列的中心部分是一个双嵌套循环。不难看出，冒泡排序的时间复杂度为O(n^2)。这是一个非常大的时间承诺。所以除了它迷人的名字之外，这种起泡的品种似乎没有什么可提供的