插入排序

孙泽辉

发布于：2021年9月2日

字数：975字

时长：4分钟

次浏览

插入排序又分为直接插入排序、折半插入排序和希尔排序。

直接插入排序

代码：

function solution(arr: number[]): Array<number> {
  for (let i = 1; i < arr.length; i++) {
    // 移动指针
    let p = i - 1;
    // 岗哨
    let x = arr[i];
    while (p >= 0 && arr[p] > x) {
      // 如果没越界并且移动指针的元素大于岗哨
      //  则将元素往前挪（腾出待插入的空来），可以覆盖arr[i]
      arr[p + 1] = arr[p];
      p--;
    }
    // 把腾出的空填上岗哨元素
    arr[p + 1] = x;
  }
  return arr;
}
console.log(solution([45, 38, 66, 90, 88, 10, 25, 45]));

/*
output:
[ 10, 25, 38, 45,45, 66, 88, 90 ]
*/

算法分析：

时间复杂度：$O(n^2)$ 最坏情况下整个数组都是倒序，每次插入都要找到第0号元素

空间复杂度：$O(1)$ 用到了哨兵变量，常数阶

由于相同的元素没有发生位置上的相对变化，是稳定的排序算法

折半插入排序

在直接插入排序中，每次向前寻找待插入位置是线性地查找，实际上前面已经是排好序的，可以使用二分查找。

function binarySearch(
  arr: number[],
  x: number,
  left: number,
  right: number
): number {
  let [l, r] = [left, right];
  while (l < r) {
    const mid = (l + r) >> 1;
    if (arr[mid] < x) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return r;
}

function solution(arr: number[]): Array<number> {
  for (let i = 1; i < arr.length; i++) {
    // 移动指针
    let p = i - 1;
    // 岗哨
    let x = arr[i];
    // 二分查找插入位置
    const pos = binarySearch(arr, x, 0, p);

    while (p >= 0 && p > pos) {
      // 将算出来的位置之前的元素往后挪腾空
      //  [ pos, p ]
      arr[p + 1] = arr[p];
      p--;
    }

    // 把腾出的空填上岗哨元素
    arr[pos] = x;
  }
  return arr;
}
console.log(solution([45, 38, 66, 90, 88, 10, 25, 45]));

/*
output:
[ 10, 25, 38, 45,45, 66, 88, 90 ]
*/

算法分析：

时间复杂度：$O(n^2)$ 折半插入排序减少了平均比较次数，但元素的移动次数不变。

空间复杂度：$O(1)$ 常数阶

尽管直接插入排序和折半插入排序时间复杂度相同，但是折半插入排序减少了比较次数，所以就平均性能而言，折半插入排序优于直接插入排序。

希尔排序

希尔排序使用步长划分局部排序，局部排序使用插入排序，元素要挪动的距离变小了从而把原本 $O(n^2)$ 的时间复杂度降低到 $O(nlog2n)$ 。

arr = [9, 8, 7, 6, 5, 4, 3, 2, 1]

def shellSort(arr):
    interval = len(arr) // 2
    while interval > 0:
        # 步长为4的插入排序
        for i in range(interval, len(arr)):
            temp = arr[i]
            k = i - interval
            while k >= 0 and temp < arr[k]:
                arr[k + interval] = arr[k]
                k -= interval
            arr[k + interval] = temp
        interval //= 2


shellSort(arr)
print(arr)

# output：
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

算法复杂度：希尔排序的时间复杂度为 $O(n^{\frac{2}{3}})$ ，希尔排序时间复杂度的下界是 $O( n*log2n)$ 。希尔排序没有快速排序算法快 $ O[n(log_2n)]$ ，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比 $O(n^2)$ 复杂度的算法快得多。

稳定性：由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

参考资料：

十大经典排序算法（动图演示） - 一像素 - 博客园 (cnblogs.com)

(27条消息) 希尔排序__YK的博客-CSDN博客_希尔排序