考研笔记

板子：直接插入、冒泡、简单选择

三个 的排序：插入是把新元素插进前面有序的部分；冒泡是相邻元素两两比较交换，每趟把最小的冒到前面；选择是每趟选出最小的，放到前面。

代码

void InsertSort(int A[], int n) {            // 直接插入排序
    for (int i = 1; i < n; i++) {            // A[0..i-1] 已经有序，把 A[i] 插进去
        int t = A[i], j = i - 1;
        while (j >= 0 && A[j] > t) {         // 比 t 大的都往后移一位
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = t;                        // j 停在第一个 <= t 的位置，t 放在它后面
    }
}
 
void BubbleSort(int A[], int n) {            // 冒泡排序（从后往前冒，每趟把最小的放到前面）
    for (int i = 0; i < n - 1; i++) {        // 第 i 趟把 A[i..n-1] 里最小的元素冒到 A[i]
        bool flag = false;                   // 这一趟有没有发生交换
        for (int j = n - 1; j > i; j--)      // 从后往前，两两比较相邻元素
            if (A[j - 1] > A[j]) {           // 逆序才交换，相等不交换
                int t = A[j - 1]; A[j - 1] = A[j]; A[j] = t;
                flag = true;
            }
        if (!flag) return;                   // 一趟下来都没交换：已经有序，提前结束
    }
}
 
void SelectSort(int A[], int n) {            // 简单选择排序
    for (int i = 0; i < n - 1; i++) {        // 第 i 趟从 A[i..n-1] 里选最小的，放到 A[i]
        int min = i;                         // 记下最小元素的下标
        for (int j = i + 1; j < n; j++)
            if (A[j] < A[min]) min = j;
        if (min != i) { int t = A[i]; A[i] = A[min]; A[min] = t; }   // 每趟只交换一次
    }
}

三者对照

最好平均 / 最坏空间稳定每趟的效果
直接插入（已经有序）稳定前面一段有序，但不一定在最终位置
冒泡（要带 flag）稳定每趟有一个元素到达最终位置
简单选择不稳定每趟有一个元素到达最终位置

关键边界

代码为什么
插入：A[j] > t，不写 >=相等的元素不往后移，t 就插在它后面，保证稳定
插入：j >= 0 写在 && 前面j 变成 时先停下来，不会访问 A[-1]
冒泡：j > i前 i 个已经在最终位置，不用再比较
冒泡：flag有了它，最好情况才是 。教材表 8.1 的 就是按带 flag 的版本给的
选择：先找 min，最后只交换一次所以简单选择的移动次数少，但比较次数和初始序列无关，永远是

易错点

  • 教材的直接插入排序下标从 1 开始，把 A[0] 当哨兵（先存 A[i]），省掉 j >= 0 的判断。和这里的写法等价。
  • 简单选择不稳定，教材反例：{2, 2*, 1}，第一趟 1 和前面的 2 交换，得到 {1, 2*, 2}，两个 2 的相对次序变了。
  • 冒泡也可以从前往后冒，每趟把最大的放到末尾。手算题要看清楚题目用的是哪个方向。

链接

反向链接