插入排序

哨兵的作用

1. Save the copy before moving the location（The algorithm itself needs it）
2. Determining boundaries reduces judgment（One less optimization of conditional judgment）

1. 直接插入排序

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

视L[1 ~ n]List to be sorted,L[0]Get ready for a sentry position,目的是将LSorting is an increasing sequence

排序过程中,会出现 L[1 ~ i]有序,L[i+1 ~ n]待排,将L[i+1]插入L[1 ~ i]suitable location

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时, must break out of the loop
            L[j + 1] = L[j];
        }
        L[j + 1] = L[0]
    }
}

Sometimes it can be awkward to use sentinels for provided arrays,The sentinel-free writing is given below.

int i, j, tmp;
for (int i = 1; i < n; i++) {
    
    if (L[i] < L[i - 1]) {
    
        tmp = L[i];
        // j >= 0 Must be written in front,否则L[j]会越界
        for (j = i - 1; j >= 0 && tmp < L[j]; j--) {
    
            L[j + 1] = L[j];
        }
        L[j + 1] = tmp;
    }
}

2. 折半插入排序

• 时间复杂度O(nlog₂n)
• 空间复杂度O(1)
• 稳定
• Only lookups are optimized,Shift operations are not optimized
• 适用：顺序存储的线性表

视L[1 ~ n]List to be sorted,L[0]Get ready for a sentry position,目的是将LSorting is an increasing sequence

Direct insertion sort is a shift while searching,而由于L[1 ~ i]有序,You can find the right position by searching in half

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) Left closed right open fold half to find
        while (l < r) {
    
            m = l + ((r - l) >> 1);
            if (L[m] <= L[0]) l = m + 1;
            else r = m;
        }
        // 第一个大于L[0]The numbers are subscripted asl或r,因为l==r
        for (j = i - 1; j >= r; j--) {
    
            L[j + 1] = L[j];
        }
        L[r] = L[0];
    }
}

Sometimes it can be awkward to use sentinels for provided arrays,The sentinel-free writing is given below.

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;
    }
}

3. 希尔排序

• 时间复杂度依赖于增量序列的函数,当nin a certain range,时间复杂度约为O(n^1.3),Worst degradation is O(n²)
• 空间复杂度O(1)
• 不稳定
• 适用：顺序存储的线性表

Change the original table to a different sync lengthdDivide into subtables,Then perform an insert sort on the child table.

d = 1时,Degenerates to direct insertion sort;But sorted by previous subtable,The original table has been relatively ordered,So sorting is faster.

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;
        }
    }
}

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;
}

// 折半插入排序
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;
}

// 希尔排序
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;
}