希尔排序
希尔排序并不能见名知意，因为希尔排序的名称起源于它的发明者Donald Shell。
基本思想：希尔排序是每次比较相邻一定间隔的元素（而每次需要相邻多少个元素进行比较，是由一个增量序列来决定的。因此，希尔排序有时也叫做缩小增量排序），直到只比较相邻元素的最后一趟排序为止。因此使用希尔排序时，每趟排序先将所有元素按某个增量d分成若干组子序列，对每个子序列进行排序。
增量序列h1，h2，…..ht ,只要h1=1，任何增量序列都是可以的，但是有些增量序列 会比另外的增量序列要更好。
数组A
A[0]
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[7]
A[8]
A[9]
A[10]
A[11]
A[12]
初始
81
94
11
96
12
35
17
95
28
58
41
75
15
Inc=6排序后
15
94 11 58 12 35 17 95 28 96 41 75 81Inc=3排序后
15
12 11 17 41 28 58 94 35 81 95 75 96Inc=1排序后
11
12
15
17
28
35
41
58
75
81
94
95
96
原理分析：
如图所示，初始增量为6，将数组A中相邻间隔为6的元素进行比较。
因此：
A[0]、A[6]进行比较
A[1]、A[7]进行比较
A[2]、A[8]进行比较
A[3]、A[9]进行比较
A[4]、A[10]进行比较
A[5]、A[11]进行比较
A[0]、A[6]、A[12]进行比较
第二趟增量为3，将数组A中相邻间隔为3的元素进行比较。
因此：
A[3]、A[0]进行比较
A[4]、A[1]进行比较
A[5]、A[2]进行比较
A[6]、A[3]、A[0]进行比较
A[7]、A[4]、A[1]进行比较
A[8]、A[5]、A[2]进行比较
A[9]、A[6]、A[3]、A[0]进行比较
A[10]、A[7]、A[4]、A[1]进行比较
A[11]、A[8]、A[5]、A[2]进行比较
A[12]、A[9]、A[6]、A[3]、A[0]进行比较
第三趟增量为1，将数组A中相邻间隔为1的元素进行比较。
因此：
A[1]、A[0]进行比较
A[2]、A[1]、A[0]进行比较
A[3]、A[2]、A[1]、A[0]进行比较
A[4]、A[3]、A[2]、A[1]、A[0]进行比较
A[5]、A[4]、A[3]、A[2]、A[1]、A[0]进行比较
A[6]、A[5]、A[4]、A[3]、A[2]、A[1]、A[0]进行比较
A[7]、A[6]、A[5]、A[4]、A[3]、A[2]、A[1]、A[0]进行比较
A[8]、A[7]、A[6]、A[5]、A[4]、A[3]、A[2]、A[1]、A[0]进行比较
A[9]、A[8]、A[7]、A[6]、A[5]、A[4]、A[3]、A[2]、A[1]、A[0]进行比较
A[10]、A[9]、A[8]、A[7]、A[6]、A[5]、A[4]、A[3]、A[2]、A[1]、A[0]进行比较
A[11]、A[10]、A[9]、A[8]、A[7]、A[6]、A[5]、A[4]、A[3]、A[2]、A[1]、A[0]进行比较
A[12]、A[11]、A[10]、A[9]、A[8]、A[7]、A[6]、A[5]、A[4]、A[3]、A[2]、A[1]、A[0]进行比较
程序实现：
#include<iostream> using namespace std; void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; } void ShellInsertSort(int a[], int n, int dk) { int i,j,p; int Tmp; for(i=dk;i<n;i++) { Tmp=a[i]; for(j=i;j>=dk;j-=dk) if(Tmp<a[j-dk]) a[j]=a[j-dk]; else break; a[j]=Tmp; print(a,n,i); } } /** * 先按增量d（n/2,n为要排序数的个数进行希尔排序 * */ void shellSort(int a[], int n){ int dk = n/2; while( dk >= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; } } int main(){ int a[13] = {81,94,11,96,12,35,17,95,28,58,41,75,15}; shellSort(a,13); system("pause"); return 0; }
分析：
希尔排序需要三层for循环，第一层for循环确定每趟希尔排序的增量，第二层循环确定哨兵元素位置，第三层for循环比较从哨兵元素到位置0上每相邻dk元素的大小，并将哨兵元素放到合适位置上。在程序中我们采用和插入排序相同的方法避免明显的使用交换。
我们将增量选择为n/2,但并不是最好的，希尔排序的时间界与增量序列的选取有关。
