希尔排序也是八大排序算法之一，它是在插入排序的基础上演变而来的，也称缩小增量排序，是直接插入排序
算法的一种更高效的改进版本。希尔排序是非稳定排序算法。其排序原理是：
将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的步长的子序列，对各个子序列进行插入排序；然后再选择一个更小的步长，再将数组分割为多个子序列进行排序......最后选择步长为1，即使用直接插入排序，使最终数组成为有序。
如现在有一组数据：[3, 1, 8, 6, 2, 5, 9, 4, 7]
使用希尔排序对这组数据进行排序，具体流程：
第一趟排序：选择步长为4
3 1 8 6 2 5 9 4 7
选择步长为4，那么：
[3, 2, 7]构成了一个子序列，这个子序列的排序结果为[2,3,7];
[1, 5]构成了一个子序列，这个子序列的排序结果为[1, 5];
[8, 9]构成了一个子序列，这个子序列的排序结果为[8, 9];
[6, 4]构成了一个子序列，这个子序列的排序结果为[4, 6];
所以第一趟的排序结果为：
2 1 8 4 3 5 9 6 7
第二趟排序：选择步长为2
2 1 8 4 3 5 9 6 7
选择步长为2，那么：
[2, 8, 3, 9, 7]构成了一个子序列，这个子序列的排序结果为[2, 3, 7, 8, 9];
[1, 4, 5, 6]构成了一个子序列，这个子序列的排序结果为[1, 4, 5, 6];
后面从8开始的和第一个子序列一样，就不用继续分了。
所以第二趟的排序结果为：
2 1 3 4 7 5 8 6 9
这样一看我们就十分接近排序结果了。
第三趟排序：选择步长为1
2 1 3 4 7 5 8 6 9
选择步长为1，就是对这组数据进行直接插入排序，所以最后就可以得出排序结构。
1 2 3 4 5 6 7 8 9
还有疑问的话现在上图，看能否帮助我们更好的理解。
已知的最好步长序列由Marcin Ciura设计（1，4，10，23，57，132，301，701，1750，…） 这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换”。用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
希尔排序的代码就是根据直接插入排序来改就行了，特别记住当我们的步长为1时，就是调用的直接插入排序。说了这么多，就算原理理解了我们最终还是要会写代码才行：
public static void shellSort(int[] array,int step){
for(int k=0; k<step; k++){ //对步长的定位,选择每次操作的开始位置
for(int i=k+step;i<array.length;i=i+step){
int j=i;
int target = array[i];
while(j>step-1 && target<array[j-step]){
array[j] = array[j-step];
j = j-step;
}
array[j] = target;
}
}
}
当我们使用希尔排序的时候，就根据步长多调用几次这个方法就行了，一般最多3次就够用了。
希尔排序的应用场景：当我么每做一次操作数据就需要排序一次的，这种情况用希尔排序效率最高，就像QQ游戏里的打麻将，摸一张打一张这种场景。
网友评论