第23讲：交换排序——冒泡排序与快速排序

交换排序，说白了就是通过不断交换元素位置来达到有序。这类算法里最经典的两个代表，就是冒泡排序和快速排序。一个简单到让人一眼看穿，一个高效到成为工业级标配。今天我们就来好好聊聊它们。

23.1 冒泡排序：最朴素的交换

冒泡排序的思路，我估计你闭着眼睛都能说出来：从头到尾，两两比较，大的往后冒。每一轮下来，最大的那个数就像气泡一样浮到末尾。

代码实现也很直白：

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 每一轮把最大的冒到最后
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

嗯，这里要注意一个优化点。如果某一轮下来一次交换都没发生，说明数组已经有序了。我曾经在项目里处理一个几乎有序的日志时间戳排序，没加这个优化，跑了整整一轮才发现白费功夫。

冒泡排序的时间复杂度是 O(n²)，空间复杂度 O(1)。稳定排序。说实话，除了教学价值，实际项目中很少用它。但它的思想——两两比较交换——是快速排序的基石。

23.2 快速排序：分而治之的典范

快速排序，简称快排。它的核心思想是：选一个枢轴（pivot），把比它小的放左边，比它大的放右边，然后递归处理左右两边。

我刚开始学快排时，总觉得它和冒泡没什么关系。后来才意识到，快排其实就是冒泡的升级版——冒泡每次只能消除一个逆序对，而快排一次 partition 能消除大量逆序对。

标准快排代码：

int partition(int arr[], int low, int high) {
    int pivot = arr[low];  // 选第一个元素做枢轴
    int i = low, j = high;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        if (i < j) arr[i++] = arr[j];
        while (i < j && arr[i] <= pivot) i++;
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    return i;
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

快排的平均时间复杂度是 O(n log n)，最坏情况 O(n²)。为什么会退化到 O(n²)？说白了就是每次选的枢轴都恰好是最大或最小值，导致 partition 后一边倒。

23.3 枢轴选择优化：三数取中法

怎么避免最坏情况？核心就是让枢轴尽量接近中位数。三数取中法就是最常用的手段：取左端、中间、右端三个元素，选它们的中位数做枢轴。

我个人习惯这样实现：

int median_of_three(int arr[], int low, int high) {
    int mid = low + (high - low) / 2;
    // 让 arr[low] <= arr[mid] <= arr[high]
    if (arr[low] > arr[mid]) swap(&arr[low], &arr[mid]);
    if (arr[low] > arr[high]) swap(&arr[low], &arr[high]);
    if (arr[mid] > arr[high]) swap(&arr[mid], &arr[high]);
    // 把中位数放到 low+1 位置，作为枢轴
    swap(&arr[mid], &arr[low + 1]);
    return arr[low + 1];
}

然后在 partition 里用这个中位数做枢轴。这样即使数组已经有序，枢轴也不会是极端值。我在项目中处理过几十万条用户行为数据，用了三数取中后，快排的性能非常稳定，再也没有出现过 O(n²) 的情况。

23.4 知识体系图

下面这张图帮你理清交换排序的脉络：

23.5 两种排序对比

特性	冒泡排序	快速排序
平均时间复杂度	O(n²)	O(n log n)
最坏时间复杂度	O(n²)	O(n²)（可优化）
空间复杂度	O(1)	O(log n)（递归栈）
稳定性	稳定	不稳定
适用场景	小规模数据、教学	大规模数据、工业级

好了，交换排序就聊到这里。冒泡排序让你理解交换的本质，快速排序让你见识分治的威力。三数取中法这个小优化，在实际项目中能帮你省下不少排查性能问题的时间。我曾经在一个线上服务里，就因为没加这个优化，导致高峰期排序耗时暴涨，排查了半天才发现是枢轴选择的问题。从那以后，我写快排必加三数取中。