前提条件：

-大多数情况下，为了简单起见只讨论从小到大的排序
-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, ... }—94i –92i +1或4i –32i +1
 猜想:Tavg =O(N7/6 ),
Tworst =O(N4/3 )