前提条件：
-大多数情况下，为了简单起见只讨论从小到大的排序
-N是正整数
-只讨论基于比较的排序（< > =有定义）
-只讨论内部排序，即加载到内存中的排序
相关概念
-稳定性：排序前相等的两个元素，排序后相对位置没有发生改变
-时间复杂度:时间复杂度是定量描述一个算法的运行的时间，一般与算法输入值的长度N有关，常用大O符号表述;
-O表示上界，Ω代表下界，θ代表即是下界也是上界即没有好坏之分;
现在我们需要了解几个定义
定义：
逆须对：对于下标i<j,如果A[i]>A[j],则称(i,j)是一对逆序对；
定理：
-任意N个不同元素组成的序列平均具有N(N-1)个逆序对；
-任何仅以交换两个相邻元素的排序算法，其平均时间复杂度为Ω(n^2),O表示上界，Ω代表下界，θ代表即是下界也是上界即没有好坏之分；
因此要提高算法效率就要每次消去多个逆序对，即交换相隔较远的元素;因此便引入了希尔排序
示例图
希尔排序.jpg
-
定义一组逐渐递减的增量序列(就理解为一组数就行，后期要用他们的值做间隔，所以叫增量)，满足前一个整数比第二个整数大，并且最后一个数为1，即：D(N) > D(N-1) > D(N-2) > ... >D(1) = 1;例如上图中的：(5,2,1)
增量序列可以随便制定，但要遵循以上原则；
-
按照增量序列的值，从大到小，每次按D(k)位置的值大小的间隔进行排序，即（k = 1,2,3),D(k）＝ 5，2，1；
注意: D(k)间隔有序的序列，在进行D(k-1)间隔排序后，仍然是D(K)间隔有序的
统一的入口
void X_sort(int arr[] ,int N)
ElenmentType 为数组类型 N 为数中元素的个数
主函数
/原始希尔排序
//使增量序列的值每次减半
void Shell_Sort(int arr[], int n){
for (int d = n/2 ; d>0 ; d = d/2){//增量序列循环
//做间隔为d的插入排序
for (int p = d; p < n; p = p+1) {
//取出每次循环的第一个数放入临时变量
int tmp = arr[p];
//类似a[i] > a[i-1] 把1替换为间隔d
for (int i = p ; i >=d && arr[i-d] > tmp; i = i-d) {
//交换 a[i] 与a[i-1] 此时tmp中存的就是a[i]
arr[i] = arr[i-d];
arr[i-d] = tmp;
}
}
}
}
测试
int main(int argc, const char * argv[]) {
//数组
int arr[9] = {6,1,5,8,7,3,2,9,4};
//希尔排序
Shell_Sort( arr, 9);
return 0;
}
输出
Printing description of arr:
(int [9]) arr = ([0] = 1, [1] = 2, [2] = 3, [3] = 4, [4] = 5, [5] = 6, [6] = 7, [7] = 8, [8] = 9)
时间复杂度：
没有一种排序在任何情况下都是表现最好
最好情况：顺序 T = O(N)
最坏情况：逆序 θ = (N^2)
最坏情况的例子
最坏情况.png
我们发现当增量元素不互质时，则小增量根本不起作用，导致前边的增量排序都浪费了
因此有人提出了其他增量方法
Hibbard 增量序列
Dk =2k –1 —相邻元素互质
最坏情况:T=(N3/2 )
猜想:Tavg =O(N5/4 )
Sedgwick增量序列
{1, 5, 19, 41, 109, ... }—94i –92i +1或4i –32i +1
猜想:Tavg =O(N7/6 ),
Tworst =O(N4/3 )
