插入排序

---

---

哨兵的作用

1. 保存移动位置前的副本（算法本身需要）
2. 确定边界减少判断（少一个条件判断的优化）

1. 直接插入排序

• 时间复杂度O(n²)
• 空间复杂度O(1)
• 稳定
• 适用：顺序存储和链式存储的线性表

视L[1 ~ n]为待排序表，L[0]准备放哨兵位置，目的是将L排序为递增序列

排序过程中，会出现 L[1 ~ i]有序，L[i+1 ~ n]待排，将L[i+1]插入L[1 ~ i]合适位置即可

int i, j;
for (i = 2; i <= n; i++) {
    if (L[i] < L[i - 1]) {
        L[0] = L[i];	// 哨兵
        for (j = i - 1; L[0] < L[j]; j--) { // j == 0时， 必跳出循环
            L[j + 1] = L[j];
        }
        L[j + 1] = L[0]
    }
}
1
2
3
4
5
6
7
8
9
10

有时提供的数组使用哨兵会很别扭，以下给出无哨兵写法。

int i, j, tmp;
for (int i = 1; i < n; i++) {
    if (L[i] < L[i - 1]) {
        tmp = L[i];
        // j >= 0 一定写在前面，否则L[j]会越界
        for (j = i - 1; j >= 0 && tmp < L[j]; j--) {
            L[j + 1] = L[j];
        }
        L[j + 1] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11

2. 折半插入排序

• 时间复杂度O(nlog₂n)
• 空间复杂度O(1)
• 稳定
• 仅优化了查找，未优化移位操作
• 适用：顺序存储的线性表

视L[1 ~ n]为待排序表，L[0]准备放哨兵位置，目的是将L排序为递增序列

直接插入排序是边查边移位，而由于L[1 ~ i]有序，可以通过折半查找找到合适位置

int i, j;
int l, r, m;
for (int i = 2; i <= n; i++) {
    if (L[i] < L[i - 1]) {
        L[0] = L[i];	// 哨兵
        l = 1, r = i; // [l,r) 左闭右开折半查找
        while (l < r) {
            m = l + ((r - l) >> 1);
            if (L[m] <= L[0]) l = m + 1;
            else r = m;
        }
        // 第一个大于L[0]的数下标为l或r，因为l==r
        for (j = i - 1; j >= r; j--) {
            L[j + 1] = L[j];
        }
        L[r] = L[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

有时提供的数组使用哨兵会很别扭，以下给出无哨兵写法。

int i, j, tmp;
int l, r, m;
for (i = 1; i < n; i++) {
    if (L[i] < L[i - 1]) {
        tmp = L[i];
        l = 0, r = i;
        while (l < r) {
            m = l + ((r - l) >> 1);
            if (L[m] <= tmp) l = m + 1;
            else r = m;
        }
        for (j = i - 1; j >= r; j--) {
            L[j + 1] = L[j];
        }
        L[r] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3. 希尔排序

• 时间复杂度依赖于增量序列的函数，当n在某一特定范围，时间复杂度约为O(n^1.3),最坏退化为O(n²)
• 空间复杂度O(1)
• 不稳定
• 适用：顺序存储的线性表

将原表以不同步长d划分为子表，然后对子表进行直接插入排序。

d = 1时，退化为直接插入排序；但通过之前的子表排序，原表已相对有序，所以排序速度更快。

int d, i, j, tmp;
for (d = n / 2; d >= 1; d >>= 1) {
    for (i = d; i < n; i++) {
        if (L[i] < L[i - d]) {
            tmp = L[i];
            for (j = i - d; j >= 0 && tmp < L[j]; j -= d) {
                L[j + d] = L[j];
            }
            L[j + d] = tmp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

4. 例

LeetCode 912. 排序数组

// 直接插入排序
int* sortArray(int* nums, int numsSize, int* returnSize)
{
    int i, j, temp;
    *returnSize = numsSize;
    for (i = 1; i < numsSize; i++) {
        if (nums[i] < nums[i - 1]) {
            temp = nums[i];
            for (j = i - 1;  j >= 0 && temp < nums[j]; j--) {
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = temp;
        }
    }
    return nums;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// 折半插入排序
int* sortArray(int* nums, int numsSize, int* returnSize)
{
    int i, j, temp;
    int l, r, m;
    *returnSize = numsSize;
    for (i = 1; i < numsSize; i++) {
        if (nums[i] < nums[i - 1]) {
            temp = nums[i];
            l = 0, r = i;
            while (l < r) {
                m = l + ((r - l) >> 1);
                if (nums[m] <= temp) l = m + 1;
                else r = m;
            }
            for (j = i - 1; j >= r; j--) {
                nums[j + 1] = nums[j];
            }
            nums[r] = temp;
        }
    }
    return nums;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 希尔排序
int* sortArray(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    int d, i, j, tmp;
    for (d = numsSize / 2; d >= 1; d >>= 1) {
        for (i = d; i < numsSize; i++) {
            if (nums[i] < nums[i - d]) {
                tmp = nums[i];
                for (j = i - d; j >= 0 && tmp < nums[j]; j -= d) {
                    nums[j + d] = nums[j];
                }
                nums[j + d] = tmp;
            }
        }
    }
    return nums;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18