文 | 莫若吻
（注：如果想更好的理解希尔排序，请先看看我的上一篇博客插入排序，希望会对你有帮助。）
一、简介
希尔排序(Shell Sort)是插入排序的一种算法，是对直接插入排序的一个优化，也称缩小增量排序。
希尔排序是非稳定排序算法。
希尔排序因DL．Shell于1959年提出而得名。
（注：为方便记忆算法，我习惯将其记作“三层for循环+if” ------** for（for（for（if）））**）
</br>
希尔排序是基于直接插入排序的以下两点性质而提出的改进方法：
1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2.插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
二、原理
希尔排序是将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。
**增量d 的范围： **1<= d < 待排序数组的长度 （d 需为 int 值）
**增量的取值： **一般的初次取序列（数组）的一半为增量，以后每次减半，直到增量为1。
第一个增量=数组的长度/2,
第二个增量= 第一个增量/2,
第三个增量=第二个增量/2,
以此类推，最后一个增量=1。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
三、原理过程图解
四、时间复杂度
**希尔排序的执行时间依赖于增量序列。 **
希尔排序耗时的操作有：比较 + 后移赋值。
时间复杂度情况如下：（n指待排序序列长度）
1) 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
2) 最坏情况：O(nlog2n)。
3) 渐进时间复杂度（平均时间复杂度）：O(nlog2n)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n²)好一些。
希尔算法的性能与所选取的增量（分组长度）序列有很大关系。只对特定的待排序记录序列，可以准确地估算比较次数和移动次数。想要弄清比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。
希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。希尔排序没有快速排序算法快，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
（注：专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。）
五、希尔排序的时间性能优于直接插入排序
①当文件初态基本有序时，直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和 n² 的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n²)差别不大。（n指待排序序列长度）
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量d 逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插入排序有较大的改进。
六、性能分析（稳定性）
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
七、示例代码（Java）
1.核心代码（升序排列为例）
（注：为方便记忆算法，我习惯将其记作“三层for循环+if” ------ for（for（for（if））））
public static int[] insertionSort(int[] arr){
if(arr == null || arr.length <= 1){
return arr;
}
//希尔排序 升序
for (int d = arr.length / 2;d>0;d /= 2){ //d：增量 7 3 1
for (int i = d; i < arr.length; i++){
//i:代表即将插入的元素角标，作为每一组比较数据的最后一个元素角标
//j:代表与i同一组的数组元素角标
for (int j = i-d; j>=0; j-=d){ //在此处-d 为了避免下面数组角标越界
if (arr[j] > arr[j + d]) {// j+d 代表即将插入的元素所在的角标
//符合条件，插入元素（交换位置）
int temp = arr[j];
arr[j] = arr[j + d];
arr[j + d] = temp;
}
}
}
}
return arr;
}
2.希尔排序详细示例代码
import java.util.*;
public class ShellSortDemo {
public static void main(String[] args) {
int[] arr = {99, 5, 69, 33, 56, 13, 22, 55, 77, 48, 12, 88, 2,69,99};
System.out.println("排序之前数组：");
printArray(arr);
//希尔排序
insertionSort(arr);
System.out.println("希尔排序后数组：");
System.out.println(Arrays.toString(arr));
}
private static int[] insertionSort(int[] arr){
if(arr == null || arr.length <= 1){
return arr;
}
//希尔排序 升序
for (int d = arr.length / 2;d>0;d /= 2){ //d：增量 7 3 1
System.out.println("增量取值:" + d);
for (int i = d; i < arr.length; i++){
//i:代表即将插入的元素角标，作为每一组比较数据的最后一个元素角标
//j:代表与i同一组的数组元素角标
for (int j = i-d; j>=0; j-=d){ //在此处-d 为了避免下面数组角标越界
// System.out.println("i:" + i + " j:" + j +" j+d="+(j+d));
if (arr[j] > arr[j + d]) {// j+d 代表即将插入的元素所在的角标
//符合条件，插入元素（交换位置）
swap(arr,j,j+d);
}
}
}
/*测试:此段代码只为查看希尔排序的每次增量变化过程，正常写程序时不要添加星号注释的这部分代码*/
for (int m = 0; m < arr.length; m++) {
System.out.print(arr[m] + " ");
}
System.out.println("");
/**/
}
return arr;
}
/*
发现无论什么排序。都需要对满足条件的元素进行位置置换。
所以可以把这部分相同的代码提取出来，单独封装成一个函数。
*/
public static void swap(int[] arr,int a,int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/*
* 最近才知道打印数组不用自己写方法这么麻烦，java API中就有 Arrays.toString(arr);
* 越简单的越容易忽略，这是最后一次自己写这个方法，以后就用自带的方法
*/
public static void printArray(int[] arr)
{
System.out.print("[");
for(int x=0; x<arr.length; x++)
{
if(x!=arr.length-1){
System.out.print(arr[x]+", ");
}else{
System.out.println(arr[x]+"]");
}
}
}
}
运行结果：（原理过程可自行测试，运行出过程，得到结果）
版权声明：本文为博主原创文章，转载请必须注明出处，谢谢！
