、夕月的博客

插入排序

2021/2/18

# Heading

插入排序的思想是每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。由插入排序的思想可以引申出三种排序算法：直接插入排序、折半插入排序和希尔排序。

# 直接插入排序

点击查看代码 
/**
 * 直接插入排序
 * @param {*} arr 
 * @param {*} n 
 */
export function InsertSort(arr = [], n = 0) {
    let tmp, j;
    for (let i = 1; i < n; i++) {
        if (arr[i] < arr[i - 1]) {
            tmp = arr[i]
            j = i
            while (tmp < arr[j - 1]) {
                arr[j] = arr[j - 1]
                j--
            }
            arr[j] = tmp
        }
    }
    return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

性能分析如下：

  • 空间效率：仅使用了常数个辅助单元，时间复杂度为O（1）。
  • 时间效率：排入元素的操作执行了n-1趟，每趟操作都分为关键字比较和移动元素，而比较和移动次数取决于待排序表的初始状态。时间复杂度为O（n^2）
    • 在最好的情况下，表中元素已经有序，每一趟只需要比较一次元素而不用移动元素，时间复杂度为O（n）
    • 在最坏情况下，表中元素恰好倒序，总的比较次数达到最大（1+3+..+n-1），总的移动次数也达到最大（2+3+..+n）
    • 平均情况下，元素是随机的，可以取最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为n^2/4
  • 稳定性：每次插入元素时总是从后向前比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是稳定的排序算法
  • 适用性：直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前向后查找指定元素的位置。大部分排序算法仅适用于顺序存储的线性表

# 折半插入排序

从直接插入排序算法中可以看出每趟插入过程都进行了两项工作：

  1. 从前面的有序子序列中查找待插入位置
  2. 给插入位置腾出空间，将待插入元素复制到插入位置
    注意到该算法中总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一移动待插入位置之后的所有元素。
点击查看代码 
/**
 * 折半插入排序
 * @param {*} arr 
 * @param {*} n 
 */
export function BinaryInsertSort(arr = [], n = 0) {
    let tmp, low, high, mid;
    for (let i = 1; i < n; i++) {
        if (arr[i] < arr[i - 1]) {
            tmp = arr[i]
            low = 0
            high = i - 1
            //二分寻找插入位置high+1
            while (low <= high) {
                mid = ~~(low + (high - low) / 2);
                if (arr[mid] > tmp) high = mid - 1
                else low = mid + 1
            }
            for (let j = i; j > high; j--) {
                arr[j] = arr[j - 1]
            }
            arr[high + 1] = tmp
        }
    }
    return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

折半插入排序相比于直接插入排序仅减少了比较元素的次数，约为O（nlog2n），该比较次数与待排序表的初始状态无关，仅取决于元素个数n。移动次数未发生变化。因此折半插入排序的时间复杂度仍未O（n^2）。折半插入排序是一种稳定的排序。

希尔排序