希尔排序，相当于插入排序的升级版。

希尔排序又称“缩小增量排序”，他也是一种属插入排序类的方法，但在时间效率上对于插入排序有较大的改进。

---

原理

基本原理
先将整个代拍记录序列分为若干子序列分别进行插入排序，带整个序列中的记录“基本有序”时，再对全体记录进行一次插入排序。
如，对数组{20,40,89,33,67,10,25,30,50}进行希尔排序时，首先需要一个哨兵数字dk（注意：dk不能为1）。

1. 假设dk=4，则需要该数组分为dk个子序列。序列1：array[0],array[4],array[8]；序列2：array[1],array[5]；序列3：array[2],array[6]；序列4：array[3],array[7]。对这四个子序列排序。
2. 令值dk=2。那么就会有两个子序列，序列1：array[0],array[2],array[4],array[6],array[8]；序列2：array[1],array[3],array[5],array[7]。对这两个子序列排序。
3. 令值dk=1。此时的序列已经基本被排好顺序了，接下来就需要对整个序列进行插入排序。得出排序结果。

---

案例

对数组array[8]={20,40,89,33,67,10,25,30,50}进行排序。

shuzu 第一趟排序 第二趟排序 最后一趟排序

---

代码

#include<iostream>
using namespace std;

void print( int array[], int length ) {
    for( int i = 0; i < length; i++ ) {
        cout << "array[" << i << "] = " << array[i] <<endl;
    }
}

void swap( int array[], int j, int k ) {
    int temp = array[j];
    array[j] = array[k];
    array[k] = temp;
}

void shellSort( int array[], int length ){
    for( int dk = 4; dk > 0; dk /= 2 ) {    //定义哨兵dk=4，每次循环dk除2 
        for( int i = dk ; i < length; i++ ) {     
            for( int j = i; j >= dk; j -= dk ){     //对子序列进行插入排序 
                if( array[j-dk] >= array[j] ){
                    swap( array, j, j-dk );
                }
            }
        }
    }
} 

int main(){
    int array[] = {20, 40, 89, 33, 67 , 10, 26, 30, 50};
    int length = sizeof(array)/sizeof(array[0]);
    shellSort( array, length );
    print( array, length );
} 

---

其他优化排序方法

希尔排序算是对于插入排序的一种优化，当然，插入排序也不仅仅有着一种优化的算法，也会有其他的，如，折半插入排序：由于插入排序是在一个有序表中进行查找和插入，因此，查找这个方法是可以通过“折半查找”来实现，由此进行的插入排序被称为这般插入排序。
在来思考选择排序。选择排序是否也可以优化呢？每一个循环的选择排序，可找出一个序列的最大值或最小值。那么，我们可以每一次遍历，找出一个最大值和一个最小值么？这便是对选择排序的优化，使得循环的次数减半。

下一次的我会为大家讲解插入排序和选择排序的其他优化算法。