排序算法（一）——插入排序（直接插入+希尔排序）
#Algorithm#排序算法#希尔排序 2018-04-01

思路

插入排序的基本思路是，每次将一个待排序的记录按照其关键码的大小插入到已经排好序的有序序列中，直到记录全部有序。 ## 直接排序

直接排序是思路最简单直接的插入排序，类似我们玩扑克牌时整理纸牌的过程。

比如我们按大小顺序排列以下纸牌（数字）

1
K 10 J 2 4 A 4 3 5 Q 2

首先，我们以第一张牌为一个有序序列，然后将第二张牌插入到该有序序列的合适位置：

1
10 K J 2 4 A 4 3 5 Q 2

这样就完成了第一次插入。此时，有序序列变为 10 K。我们继续将下一张牌插入到该有序序列中。这对于纸牌玩家来说，顺理成章，直接将 J 插到 10 和 K 之间。但对于计算机来说，可能需要进行以下过程：

  • 首先将 J 和 K 比较，K > J，所以将 K 的位置往后移动一位（数组索引加 1）。

  • 继续往前比较，发现 10 < J，所以将 J 放在 10 后面（将 10 元素索引 + 1 的位置赋值为 J）。

  • 完成该次插入，有序序列变为 10 J K。

    依照上述思路，不停的将接下来的元素插入到前面的有序序列中去，直至数组的结尾。

算法分析

从上面的例子我们大概可得直接插入的大体算法为：

  • 以第一个元素为有序序列

  • 将有序序列的后一个元素插入到有序序列中去，构成新的有序序列。

  • 继续插入下一个元素，直至数组结尾。

    从上面的思路，我们需要注意的是“插入”的操作。

    首先我们需要找到插入的合适位置，因为该算法从有序序列的后面往前查找。所以每当遇到元素大于带插入元素时，就把该元素向后移动一位，以便为插入元素“空”出位置。直到遇到小于带插入元素的元素时，合适的位置被找到，将元素插入即完成此次插入操作。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const insertionSort = arr => {
    for (let i = 1; i < arr.length; i++) {
        let tmp = arr[i]  // 暂存该元素，因为在移动操作时会覆盖掉该位置的值
        let j = i - 1 // 从有序序列的后面向前查找插入位置
        
        // 把有序序列中所有大于待插入的元素向后移动一位。
        for (; a[j] > tmp; j--) {
            arr[j + 1] = arr[j]
        }
        
        // 循环结束，插入位置被找到，插入该值，完成该次插入
        arr[j + 1] = tmp
    }
}

希尔排序

直接插入排序算法面临一个问题，当待排序数组基本无序，且长度比较长时，要进行大量的位置移动操作。性能较低。

希尔排序试图解决上述问题。

希尔排序首先将数组分割为若干个序列，首先将每个序列进行直接插入排序。然后重新分割序列，减少序列的个数，再次对每个序列分别进行直接插入排序。然后再次减少序列的个数，分别进行直接插入排序，直至序列被减少为一个，对整个数组进行一个直接插入排序即可。

通过以上算法，开始每个序列的长度很小，位置移动对性能的影响。随着序列个数的减少，序列长度的增加的同时，序列开始慢慢变得有序，使得插入插入操作减少。提高了性能。

算法分析

关于如何划分序列，尚未有人求得一个最好的方案。希尔最早提出的方案是，开始每隔 length / 2 构成一个子序列。然后每次将间隔缩小一倍，构成新的子序列，对这些子序列进行直接插入排序。直至最后间隔变为 1 则子序列变为整个序列。

任然一上面的序列为例：

1
K 10 J 2 4 A 4 3 5 Q 2
  • 第一次每隔 5 构成一个子序列，则有 5 个子序列，分别为：
1
2
3
4
5
A  2  K
10 4
J  3
2  5
4  Q

对上面子序列进行插入排序，则序列变为：

1
2
3
4
5
A  2  K
4  10
3  J
2  5
4  Q

则第一次对子序列进行插入排序后，原序列变为：

1
A 4 3 2 4 2 10 J 5 Q K
  • 然后将间隔缩小为 5 / 2 = 2 ，则子序列变为：
1
2
A 3 4 10 5 K
4 2 2 J Q

分别对子序列直接插入排序后，原序列变为：

1
A 2 3 2 4 4 5 J 10 Q K
  • 最后一次间隔缩小为 1，则子序列就变为序列本身，此时序列基本有序，直接进行直接插入排序完成排序。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const shellSort = arr => {
    // 初始间隔为 length / 2，每次缩小一倍，直到间隔变为 1
    for (let d = Math.floor(arr.length / 2); d >= 1; d = Math.floor(d / 2)) {
    
        // 对子序列进行直接插入排序
        for (let i = d; i < arr.length; i++) {
            let tmp = arr[i]
            let j = i - d
            for (; j >=0 && arr[j] > tmp; j -= d) {
                arr[j + d] = arr[j]
            }
            arr[j + d] = tmp
        }
        
    }
}

总结

直接插入排序时间复杂为 O(n^2)，是稳定的排序算法。

希尔排序的时间复杂度在 O(n^2) 和 O(nlog2n)，约为 O(n^1.3)，是不稳定的排序算法。