希尔排序又称 “缩小增量排序“
假设有一个无序的数组为 {9,5,7,6,2,4,10,1,3,8}，共有10个数
int a[10]={9,5,7,6,2,4,10,1,3,8};主要思想： 根据步长来分割数组，步长分别为 5=(10/2) 2=(5/2) 1=(2/2)；都是向下取整，直到步长为1； 步长为5时分割的数组是 {9，4}，{5，10}，{7，1}，{6，3}，{2，8} 然后对各个数组进行直接插入排序得到{4，9}，{5，10}，{1，7}，{3，6}，{2，8} 第一趟完成后：数组为{4，5，1，3，2，9，10，7，6，8} 此时步长变为2；分割数组为{4，1，2，10，6}，{5，3，9，7，8} 然后对各个数组进行直接插入排序得到{1，2，4，6，10}， {3，5，7，8，9} 第二趟结束后数组为{ 1，3，2，5，4，7，6，8，10，9} 最后步长为1时，在进行直接插入排序，可得数组 {1，2，3，4，5，6，7，8，9，10}
代码实现：
#include <iostream> using namespace std; void shellsort(int a[],int n){ int temp;//哨兵 int j; int dk; for(dk=n/2;dk>=1;dk=dk/2){ //每次步长取原来的一半，直到等于1时 for(int i=dk;i<n;i++){ //从第二个数才能开始比较，和移动 if(a[i]<a[i-dk]){ //当前的值小于当前步长数组的前一个数时 temp=a[i]; //记录该数据 for(j=i-dk;temp<a[j]&&j>=0;j-=dk){ //一直往前找，直到找到 比当前小的值或者找到哨兵 a[j+dk]=a[j]; } //此时的j的值为符合位置的前一个位置 a[j+dk]=temp; //赋给当前位置 } } } } int main(){ int a[10]={9,5,7,6,2,4,10,1,3,8}; shellsort(a,10); for(int i=0;i<10;i++){ cout<<a[i]<<" "; } cout<<endl; return 0; }