为什么快速排序比冒泡排序快？

冒泡排序

想象一排身高不同的人站成一队，你要把他们从矮到高排好。规则很简单：每次只能比较相邻两个人，如果左边比右边高，就让他们交换位置。从队伍最左边开始，一路比较到最右边，走一轮下来，最高的那个人肯定会被“冒泡”到最右端。不知道为什么起这么抽象的名字——冒泡排序。泡泡排序最后冒出来？

假设有一数组：[5, 2, 9, 1, 5]

第一轮：
比较5和2-> 5>2，交换 -> [2, 5, 9, 1, 5]
比较5和9-> 不用交换 -> [2, 5, 9, 1, 5]
比较9和1-> 9>1，交换 -> [2, 5, 1, 9, 5]
比较9和5-> 9>5，交换 -> [2, 5, 1, 5, 9]

一轮下来，最大的数字9已经排到了最右边。

第二轮（不用再管最后一位了）：
继续从头比较，把第二大的数字送到倒数第二位

以此类推，每一轮都能确定一个数字的最终位置，直到整个数组有序。

C++实现冒泡排序

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

快速排序

选一个基准值，把数组分成两部分：比基准小的放左边，比基准大的放右边。然后对左右两部分递归地重复这个过程，直到每部分只剩一个元素。

假设有：[5, 2, 9, 1, 5, 6]，选最后一个元素 6 作为基准
用一个指针 i 记录"小于基准区域"的边界，遍历数组，凡是小于基准的元素就交换到左边

[5, 2, 9, 1, 5, 6] 基准 = 6
分区后：[5, 2, 1, 5, 6, 9]

这一轮下来，6已经在它最终该在的位置上（因为左边全部比它小）。
递归处理左右两部分，直到每部分长度为 1 或 0。

C++实现快速排序

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

快排如果总是找最后一个做为基准，那么最坏情况下就是碰到有序数组：[1,2,3,4,5,6]这样就需要O(n²)，我们需要避免这种情况。

有两种策略避免快排最坏情况：随机选择基准、取中位数。

为什么快速排序比冒泡排序更快？

冒泡每一轮只能把一个数放到最终位置，问题规模每次减 1。n 个数要走 n 轮，每轮比较 O(n) 次，一共 O(n²)。

快排每次分区也要 O(n)，但分完数组就切成了两半，两半再各自去分。平均切 log n 层就到底了，每一层加起来还是 O(n)，所以一共 O(n log n)。

说白了就是：每次减半，比每次减一快太多。