爱站程序员基地希尔排序是一种插入排序算法，它出自D.L.Shell，因此而得名。Shell排序又称作缩小增量排序。Shell排序的执行时间依赖于增量序列。
希尔排序是把记录按下标的一定步长（增量）分组，对每组使用直接插入排序算法排序；随着步长逐渐减小（至1），每组包含的关键词越来越多，当步长减少至1时，整个文件恰好被分成1组，算法就此终止。
【基本步骤】
首先，先选择步长step=length/2，缩小步长继续以step=step/2的方式，这种步长选择可以用一个序列表示，{n/2，（n/2）/2，。。。，1}，称为增量序列。希尔排序选择这个序列是比较常用的，也是希尔建议的增量，称为希尔增量。但其实这个增量序列不是最优的。
原始数组：8 9 1 7 2 3 5 4 6 0
初始step=10/2=5，整个数组分为5组[8 3].[9 5].[1 4].[7 6].[2 0]
对这5组分别进行插入排序，数组变成：3 5 1 6 0 8 9 4 7 2
然后下一轮step=5/2=2，分成2组，步长为2：[3 1 0 9 7].[5 6 8 4 2]
对这两组进行插入排序，数组变成：0 2 1 4 3 5 7 6 9 8
下一轮：step=2/2=1，分成一组，步长为1:[0 2 1 4 3 5 7 6 9 8]
对这一组进行插入排序，数组最终：0123456789
【C++实现】
//总的来说就是每次步长对半劈，对分组进行直接插入排序#include <iostream>using namespace std;void shell(int *a,int n){int temp;for (int step=n/2; step>0; step=step/2) {//分组for (int k=0; k<step; k++) {//进到分组里面,k代表了某个分组for (int i=k+step; i<n; i+=step) {//找到具体的分组的某一个元素if (a[i]<a[i-step]) {temp=a[i];int j;for (j=i-step; j>=0&&a[j]>temp; j=j-step) {a[j+step]=a[j];}a[j+step]=temp;}}}}}int main(){int a[]={6,202,100,301,38,8,1};int n=sizeof(a)/sizeof(int);shell(a,n);for (int i=0; i<n; i++) {cout<<a[i]<<\" \";}}
【复杂度分析】
1.时间复杂度：最坏情况下，每两个数都要比较并交换一次，时间复杂度O（n^2）,最好情况下，数组有序，不需要交换，只需要比较，时间复杂度O（n）。
2.空间复杂度：只需要一个变量用于两数交换，与n的大小无关，空间复杂度O（1）。
