希尔排序（Shellsort），是插入排序的一种更高效的改进版本，它是使排序算法冲破O（n^2）的第一批算法。它对插入排序的改进之处在于改变了插入排序一次只能移动一位的缺点。
希尔排序通过比较相距一定间隔的元素进行排序，通过对相隔一定步长的元素进行插入排序使得整体趋向于有序，随着步长的减小慢慢有序，最后一步步长为1，也就是插入排序，保证了最后结果一定有序。
以下列数据为例
81 94 11 96 12 35 17 95 28 58 41 75 15
先取步长为5
可以将这些数据分为5组
『81 35 41』
『94 17 75』
『11 95 15』
『96 28』
『12 58』
也可以这么得到 每行5个 写下来 将每列元素进行排序
81 94 11 96 12
35 17 95 28 58
41 75 15
对每一组进行插入排序
就可以得到
35 17 11 28 12
41 75 15 96 58
81 94 95
至此以5为步长的排序结束
步长为3的时候
35 17 11
28 12 41
75 15 96
58 81 94
95
分别对每一列进行插入排序 得到
28 12 11
35 15 41
58 17 94
75 81 96
95
步长为3的排序完成
下面进行步长为1的排序，也就是对上面这个进行插入排序，就可以得到有序数列。
注意
实际在编程时，并不是分别对每一组进行排序完了之后在排序另一组，而是从下标0开始以此增加，依次比较第一列的前两个数、第二列的前两个数。。。第n列的前两个数，然后在比较第一列的第二、三个数，这样效果和每列单独排序是一样的，但是编程方便了很多。
步长的选择
常用的增量序列是Shell建议的序列 n/2 但是实际效果并不是最好。使用希尔增量的希尔排序最坏情况时间复杂度为O(n^2)。
另一种高效的增量叫做Hibbard增量：1 3 7 15 …… 2^n-1 。可以证明，使用该增量的希尔排序最坏情形时间复杂度为O（n^(2/3)）。
关于希尔排序的步长研究有很多，有兴趣的读者可以自行查找资料。
C语言实现如下
|
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 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <stdio.h> #include <stdlib.h> #include <time.h> void shell_sort(int *p, int n); int main(void) { int i; int a[1000]; srand((int)time(NULL)); for (i = 0; i < 1000; ++i) { a[i] = rand() % 1000; } shell_sort(a, 1000); for (i = 0; i < 1000; ++i) { printf("%d ", a[i]); } return 0; } void shell_sort(int *p, int n) { int i, j, gap; int tmp; for (gap = n/2; gap != 0; gap /= 2) { for (i = gap; i < n; ++i) { tmp = p[i]; for (j = i;j >= gap; j -= gap) { if (tmp < p[j - gap]) { p[j] = p[j - gap]; } else { break; } } p[j] = tmp; } } } |
支付宝打赏 
微信打赏