交换排序——冒泡与快速排序

复习定位

冒泡排序是入门排序——两两比较交换——每轮确定一个最大元素——简单但慢。快速排序是实际最常用的排序之一——平均快速但最坏可能慢——分治的典型代表。理解快排的分区过程——pivot的选择对性能影响巨大——不要选固定位置——最好随机或取中位数。

冒泡排序

冒泡排序核心——从数组第一个元素开始——依次比较相邻的两个元素——如果前面的比后面的大——交换它们。经过一轮——最大元素被"冒泡"到数组末尾。重复n-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]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

每轮确定一个最大值。如果某轮没有发生任何交换——表明数组已经有序——可以提前终止循环——复杂度降为O(n)。

快速排序的基本思想

快速排序选取一个pivot——将数组重新排列为"小于pivot的部分 | pivot | 大于pivot的部分"——然后递归地对左右两部分进行排序。

分区(partition)是快排的核心。常用的Lomuto分区算法——选择最后一个元素为pivot——i指向小于部分的末尾——遍历j——如果arr[j] < pivot——i++并交换arr[i]与arr[j]——循环结束将pivot交换到i+1位置。

pivot = 5, 数组: [3,7,1,8,4,5]
i=-1, j=0: 3<5→i=0, swap(3,3)
j=1: 7<5? 否
j=2: 1<5→i=1, swap(7,1)→[3,1,7,8,4,5]
j=3: 8<5? 否
j=4: 4<5→i=2, swap(7,4)→[3,1,4,8,7,5]
j=5 pivot→交换arr[3]和arr[5]→[3,1,4,5,7,8]
返回3——pivot位置=5在索引3

退化与优化

最坏情况——每次选的pivot都是最小(或最大)元素——分区极不平衡——递归深度O(n)→总复杂度O(n²)。最坏情况发生在pivot选首元素而数组已有序(正序或逆序)时。

避免退化：

• 随机pivot——从子数组中随机选一个元素作为pivot——消除对输入序列的依赖——几乎确保平均性能。
• 三数取中——取左、中、右三个元素的中位数作为pivot——大幅降低最坏情况概率。
• 小数组切换——当子数组长度小于阈值(如10-20)时——切换到插入排序——因为小数组中插入排序的常数更小。

快速排序的稳定性

快速排序不稳定——分区过程中交换操作可能改变同值元素的相对顺序。例如[(a,1),(b,1)]——两个元素的第二字段相同——分区时pivot选择第二个1——先将(a,1)和(b,1)比较——交换位置——顺序被打乱。

复习检查

1. 冒泡排序的时间复杂度和稳定性——冒泡排序在数据基本有序时——若不发生交换可提前终止——可以达到O(n)；但最坏情况(逆序)是O(n²)——稳定(因为相等时不交换)的特性——因此常用做链表排序——链表无法随机访问不适合快排和二分法划分。

2. 快速排序的平均时间复杂度O(n log n)是如何证明的——每次分区大致会将数组分为两部分——递归树深度O(log n)每层总处理O(n)——总时间O(n log n)来自分治问题的分析和期望随机pivot的划分均匀。

3. 快速排序的空间复杂度为什么是O(log n)——递归调用栈深度平均为O(log n)——每次递归需要保存临时参数。

4. 当数组已经是有序且pivot选首元素——快排会退化——为什么？每次划分选择pivot为第一个元素——只有一边有元素——另一部分为空——递归深度=n——总比较n²=n*(n-1)/2。

5. Hoare分区与Lomuto分区的区别——Hoare分区从两端向中间扫描——交换错位的元素——平均比较次数比Lomuto约少2倍——但实现略微复杂——也是众多标准库实现的选择。