希尔排序，相当于插入排序的升级版。
希尔排序又称“缩小增量排序”，他也是一种属插入排序类的方法，但在时间效率上对于插入排序有较大的改进。
原理
基本原理
先将整个代拍记录序列分为若干子序列分别进行插入排序，带整个序列中的记录“基本有序”时，再对全体记录进行一次插入排序。
如，对数组{20,40,89,33,67,10,25,30,50}进行希尔排序时，首先需要一个哨兵数字dk（注意：dk不能为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]。对这四个子序列排序。
- 令值dk=2。那么就会有两个子序列，序列1：array[0],array[2],array[4],array[6],array[8]；序列2：array[1],array[3],array[5],array[7]。对这两个子序列排序。
- 令值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 );
}
其他优化排序方法
希尔排序算是对于插入排序的一种优化，当然，插入排序也不仅仅有着一种优化的算法，也会有其他的，如，折半插入排序：由于插入排序是在一个有序表中进行查找和插入，因此，查找这个方法是可以通过“折半查找”来实现，由此进行的插入排序被称为这般插入排序。
在来思考选择排序。选择排序是否也可以优化呢？每一个循环的选择排序，可找出一个序列的最大值或最小值。那么，我们可以每一次遍历，找出一个最大值和一个最小值么？这便是对选择排序的优化，使得循环的次数减半。
下一次的我会为大家讲解插入排序和选择排序的其他优化算法。
