希尔排序
核心：基于插入排序，使数组中任意间隔为 h 的元素都是有序的，即将全部元素分为 h 个区域使用插入排序。其实现可类似于插入排序但使用不同增量。更高效的原因是它权衡了子数组的规模和有序性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
希尔排序是基于插入排序的以下两点性质而提出改进方法的：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
算法实现
通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
假设有数组 array = [80, 93, 60, 12, 42, 30, 68, 85, 10]，首先取 d1 = 4，将数组分为 4 组，如下图中相同颜色代表一组：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
然后分别对 4 个小组进行插入排序，排序后的结果为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
然后，取 d2 = 2，将原数组分为 2 小组，如下图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
然后分别对 2 个小组进行插入排序，排序后的结果为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
最后，取 d3 = 1，进行插入排序后得到最终结果：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
图片摘自常见排序算法 - 希尔排序 (Shell Sort)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
步长序列
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
以下是性能比较好的步长序列文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
- Shell's original sequence: N/2 , N/4 , ..., 1 (repeatedly divide by 2);
- Hibbard's increments: 1, 3, 7, ..., 2k - 1 ;
- Knuth's increments: 1, 4, 13, ..., (3k - 1) / 2 ;
- Sedgewick's increments: 1, 5, 19, 41, 109, ....
It is obtained by interleaving the elements of two sequences:
1, 19, 109, 505, 2161,….., 9(4k – 2k) + 1, k = 0, 1, 2, 3,…
5, 41, 209, 929, 3905,…..2k+2 (2k+2 – 3 ) + 1, k = 0, 1, 2, 3, …
已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)。这项研究也表明比较在希尔排序中是最主要的操作，而不是交换。用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html
实现
Java
public class ShellSort {
public static void main(String[] args) {
int[] unsortedArray = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
shellSort(unsortedArray);
System.out.println("After sorted: ");
for (int number : unsortedArray) {
System.out.print(" " + number);
}
}
private static void shellSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
int length = array.length;
int gap = length / 2;
int i, j;
for (; gap > 0; gap /= 2) { // Shell's original sequence: N/2 , N/4 , ..., 1 (repeatedly divide by 2)
for (i = gap; i < length; i += gap) {
int temp = array[i];
for (j = i; j > 0 && array[j - gap] > temp; j -= gap) {
array[j] = array[j - gap];
}
array[j] = temp;
}
}
}
}
复制代码Kotlin
object ShellSortKt {
fun shellSort(array: IntArray) {
if (array.isEmpty()) {
return
}
val size = array.size
var gap = size / 2
while (gap > 0) {
for (i in gap until size step gap) {
val temp = array[i]
var j = i
while (j > 0 && array[j - gap] > temp) {
array[j] = array[j - gap]
j -= gap
}
array[j] = temp
}
gap /= 2
}
}
}
fun main(args: Array<String>) {
val unsortedArray = intArrayOf(6, 5, 3, 1, 8, 7, 2, 4)
ShellSortKt.shellSort(unsortedArray)
println("After sorted: ")
unsortedArray.forEach {
print(" $it")
}
}
复制代码Python3
#!/usr/bin/env python
# coding=utf-8
def shell_sort(arrayList):
length = len(arrayList)
gap = length // 2
while (gap > 0):
for i in range(gap, length, gap):
holder = arrayList[i]
j = i
while (j > 0 and arrayList[j - gap] > holder):
arrayList[j] = arrayList[j - gap]
j -= gap
arrayList[j] = holder
gap //= 2
if __name__ == "__main__":
arrayList = [6, 5, 3, 1, 8, 7, 2, 4]
print("orgin array list: {0}".format(arrayList))
shell_sort(arrayList)
print("after sorted list: {0}".format(arrayList))
复制代码总结
一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用 i += step_size 而不是 i++)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4499.html