插入排序与选择排序

复习定位

插入排序和选择排序都是O(n²)的简单排序——代码很短、稳定性好(插入稳定、选择不稳定)。插入排序在基本有序的数组上逼近O(n)——因为内循环通常只需移动少数元素。选择排序的比较次数永远是n(n-1)/2——与输入数据分布无关。小规模数据(如n<50)时——由于常数低——插入排序可能比复杂的O(n log n)排序还要快——因此快排等高级排序在子数组小于阈值时会切换到插入排序。

插入排序

思路：将数组视为由已排序的前缀(初始时长度为1)和未排序的后缀组成。每次取未排序部分的第一个元素——在已排序部分从后往前扫描——找到合适的位置插入——并移动已排序元素。

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

时间复杂度——最坏(数组完全逆序)时——每轮要从i-1比较到0——共约n²/2次比较和移动——O(n²)。最好(数组已有序)时——内循环条件arr[j] > key在第一次时就为假——只进行1次比较——n个元素总共n-1次比较——O(n)。平均——元素均匀随机分布——约n²/4次比较——O(n²)。

插入排序是稳定的——当arr[j] > key时移动——相等时不会移动——所以同值元素的相对顺序被保留。

选择排序

思路：每一轮从未排序部分选出最小的元素——将其与未排序部分的第一个元素交换——该元素成为已排序部分的新末尾。

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx]) min_idx = j;
        swap(&arr[i], &arr[min_idx]);
    }
}

时间复杂度——内循环的比较次数始终为(n-i-1)——第一轮n-1、次轮n-2...总和=n(n-1)/2——O(n²)——与初始顺序无关。因此选择排序不能像插入排序那样在有序数组中加速。

选择排序是不稳定的——交换操作可能改变同值元素的原始顺序。例如[5a, 5b, 1]——第一轮将5a与1交换→[1, 5b, 5a]——5a与5b的相对顺序被改变了。

何时使用

场景	推荐	原因
n≤50	插入排序	常数极小且稳定——可能比O(n log n)还快
数组接近有序	插入排序	接近O(n)
链表	插入排序	插入元素不需移动(仅改指针)
交换代价极大	选择排序	元素移动次数为O(n)
通用	快速排序/归并	O(n log n)

复习检查

1. 插入排序在数组[3,2,5,1,4]上的完整过程——模拟show每轮结果。

2. 选择排序在数组[3,2,5,1,4]上的完整过程——模拟每轮结果。

3. 为什么插入排序在有序数组上是O(n)？while循环的条件arr[j] > key在第一次判断时就为假——最多比较一次——无需移动元素——所以每个元素O(1)的工作。

4. 插入排序和选择排序的时间复杂度是一样的——但选择排序在什么时候更优——当元素规模大且移动元素的代价远大于比较元素时——因为选择排序最多只移动n次(n次交换)——而插入排序移动次数为O(n²)——所以在大型结构体的排序中——选择排序可能更快。

5. 稳定性的意义——如果已经按姓名排序——现在按年龄稳定排序——同年龄的人仍然按照姓名的顺序(相对于之前的排序结果保持不变)。非稳定排序可能会打乱保留原顺序。