考研笔记

板子：折半插入排序与希尔排序

两个都是直接插入排序的改进。折半插入：用折半查找找插入位置，只减少比较次数，移动次数不变。希尔排序：下标相差 的元素分成一组，组内做直接插入； 逐渐减小到 1。

代码

void BInsertSort(int A[], int n) {           // 折半插入排序
    for (int i = 1; i < n; i++) {            // 把 A[i] 插进有序的 A[0..i-1]
        int t = A[i], low = 0, high = i - 1;
        while (low <= high) {                // 折半查找插入位置
            int mid = (low + high) / 2;
            if (A[mid] > t) high = mid - 1;  // 插入位置在左半
            else low = mid + 1;              // 相等也往右走：t 放在相等元素的后面，保证稳定
        }
        for (int j = i - 1; j >= high + 1; j--) A[j + 1] = A[j];   // high+1 就是插入位置，它和后面的都后移
        A[high + 1] = t;
    }
}
 
void ShellSort(int A[], int n) {             // 希尔排序：增量 d 从 n/2 开始，每次减半
    for (int d = n / 2; d >= 1; d /= 2)      // 最后一趟 d = 1，就是一次直接插入排序
        for (int i = d; i < n; i++) {        // 从每组的第二个元素开始，在组内做直接插入
            int t = A[i], j = i - d;         // 同一组里的前一个元素是 A[i-d]
            while (j >= 0 && A[j] > t) {     // 组内比 t 大的往后移 d 位
                A[j + d] = A[j];
                j -= d;
            }
            A[j + d] = t;
        }
}

复杂度：

时间空间稳定
折半插入：比较次数降到约 ，但移动次数不变稳定
希尔排序依赖增量序列，无法准确给出不稳定

关键边界

代码为什么
折半结束时插入位置是 high + 1循环退出时 low == high + 1。A[0..high] 都 ，A[low..i-1] 都 ，所以 t 放在 high + 1
A[mid] > t 往左，否则往右相等时往右找，t 就插在所有相等元素的后面，所以折半插入稳定
希尔：i 从 d 开始逐个往后不是先排完一组再排下一组，而是各组交替进行，每个 A[i] 只和自己组里前面的元素比较。结果和逐组排序一样
希尔：j -= d组内相邻两个元素的下标相差 ，不是 1

易错点

  • 折半插入只减少了比较次数，元素的移动次数和直接插入一样多，总时间仍是 。比较次数与初始序列无关，只取决于 （2012 年考过这个对比）。
  • 折半插入只能用于顺序表；直接插入顺序表、链表都能用。
  • 希尔排序的时间复杂度：考试的稳妥答案是「与增量序列有关」，不要直接写 。
  • 手算希尔排序：下标相差 的元素为一组，组内排好，其他位置不动（2014、2018 年考过根据中间结果反推增量）。

链接

反向链接