「排序算法」专题 10：冒泡排序（了解）

「排序算法」专题 10：冒泡排序（了解）

冒泡排序（了解）

前面的选择排序可以作为排序算法的入门算法，插入排序让我们看到了如何改进算法，充分利用每一轮循环的比较来加快排序的速度。冒泡排序的思想如同它的名字一样，每一轮都将一个元素「冒泡」到数组的末尾。

冒泡排序的基本思想

• 基本思想：外层循环每一次经过两两比较，把每一轮未排定部分最大的元素放到了数组的末尾；

• 依次将相邻的两个元素进行比较，把较大的元素交换到后面，这样一轮循环下来，就可以找到这一轮循环中最大的那个元素，我们把这个过程形象地称之为“冒泡”；

• 由于每一轮循环都「冒泡」出一个这一轮循环最大的元素，所以上一轮循环的最后一个元素，没有必要再参加下一轮循环的比较了；

• 「冒泡排序」有个特点：在遍历的过程中，提前检测到数组是有序的，从而结束排序，而不像「选择排序」那样，即使输入数据是有序的，「选择排序」依然需要很「死板地」地走完所有的流程。

冒泡排序第 1 版

Python 代码：

def bubble_sort_1(nums):
    n = len(nums)
    for i in range(0, n - 1):
        for j in range(0, n - i - 1):  # 注意临界值的选取
            if nums[j] > nums[j + 1]:
                swap(nums, j, j + 1)

冒泡排序第 2 版

Java 代码：

以下代码提交以后会出现超时，超时数据是规模较大的数据，一般情况下说明算法是正确的，但不高效。

public class Solution {

    // 冒泡排序：超时

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        for (int i = len - 1; i >= 0; i--) {
            // 先默认数组是有序的，只要发生一次交换，就必须进行下一轮比较，
            // 如果在内层循环中，都没有执行一次交换操作，说明此时数组已经是升序数组
            boolean sorted = true;
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    sorted = false;
                }
            }
            if (sorted) {
                break;
            }
        }
        return nums;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

Python 代码：在「冒泡」的过程中检查数组是否已经排好序，如果已经是顺序数组，整个算法就可以终止了。

def bubble_sort_2(nums):
    n = len(nums)
    for i in range(0, n - 1):
        sorted = True  # 假设数组是排好序的

        for j in range(0, n - i - 1):  # 注意临界值的选取
            if nums[j] > nums[j + 1]:
                swap(nums, j, j + 1)
                sorted = False  # 只要发现有元素交换，就说明假设是错误的
        # 如果一轮下来都没有元素交换，那么接下来的几轮就没有必要进行比较了
        if sorted:
            break

复杂度分析：

• 时间复杂度：$O(N^2)$，这里 $N$ 是数组的长度；
• 空间复杂度：$O(1)$，使用到常数个临时变量。

（本节完）