希尔排序的基本思想
希尔排序又称缩小增量排序，因 DL. Shell于 1959 年提出而得名。先将待排序表按照一定的间隔分割成多个子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，知道d=1 为止。
步骤
过程演示
- 初始序列
- 第一趟，初始增量取d=length/2=10/2=5
- 第二趟，修改增量 d =d/2=2
- 第三趟，修改增量 d=d/2=1，得到最终排序结果
算法代码
#include<iostream>usingnamespacestd; //希尔排序 voidShellSort(intnums[],intn){ intd,i,j,temp; for(d=n/2;d>=1;d/=2){ //初始增量：d/2，d=1结束 for(i=d;i<n;i++){ //每一趟使用直接插入排序 temp=nums[i]; for(j=i;j>=d&&temp<nums[j-d];j-=d){ nums[j]=nums[j-d]; } nums[j]=temp; } } } //打印数组 voidprintNum(intnumbers[],intn){ for(inti=0;i<n;i++){ cout<<numbers[i]<<" "; } } intmain() { intnumbers[10]={3,44,38,5,47,15,36,26,1,2}; intn=sizeof(numbers)/sizeof(numbers[0]); //数组长度 ShellSort(numbers,n); //调用 InsertSort 函数进行插入排序 printNum(numbers,n); //打印数组 return0; }
注：当 d=1 时，希尔排序会变成直接插入排序
算法性能分析
