希尔排序（Shell Sort）是插入排序的一种，也是直接插入排序的更高效的改进版本，希尔排序充分利用了插入排序的两个特点：
1）当数据规模小的时候非常高效。
2）当给定数据已经有序时的时间复杂度为O(n)。
所以，Shell排序每次把数据分成若干块，来使用插入排序，而且之后在这若干个小块排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停地合并小块，直到最后一个小块。
这里每次分成若干个小块是通过“增量”来控制的，开始的时候增量较大，接近n/2，从而使得分割出来接近n/2个小块，逐渐的减小“增量”，最终减小到1。
例如：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | public class Main { public static int count = 0; public static void shellSort(int[] data) { // 计算出最大的h值 int h = 1; while(h <= data.length / 3) { h = h * 3 + 1; } while(h > 0) { for(int i=h;i<data.length;i+=h) { if(data[i] < data[i-h]) { int tmp = data[i]; int j = i-h; while(j >= 0 && data[j] > tmp) { data[j+h] = data[j]; j -= h; } data[j+h] = tmp; print(data); } } // 计算出下一个h值 h = (h - 1) / 3; } } public static void print(int[] data) { for(int i=0;i< data.length;i++) { System.out.print(data[i]+"\t"); } System.out.println(); } public static void main(String[] args) { int[] data = new int[]{4,6,1,9,5,8}; print(data); shellSort(data); print(data); }} |
运行结果如下：
1 2 3 4 5 | 4 6 1 9 5 8 1 4 6 9 5 8 1 4 5 6 9 8 1 4 5 6 8 9 1 4 5 6 8 9 |
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程