定义：希尔排序又称为缩小增量排序，由D.L.Shell在1959年提出而得名。

该算法先取一个小于数据表中元素个数 n 的整数d, 并以此作为第一个间隔，将数据分为d个子序列，所有距离为d的对象存放在同一个子序列中，于是数据表中的元素就被分成了d个组，分组确定后，在每一个小组中进行直接插入排序，局部排序完成后，缩小d, 重复上述步骤，直至取到d=1时，完成最后一次直接插入排序。

为什么这个算法会起作用：开始的时候d较大，子序列中的数据较少，所以最开始的时候算法运行较快，随着算法进行，d逐渐变小，子序列中元素的个数也就越来越多，所以排序工作可能会变慢，但是由于前面已经完成了部分排序工作，因而在很大程度上减轻了后来的工作量，于是最终总体的排序速度还是比较快的。

#include using namespace std;  
  
//int a[] = {70,30,40,10,80,20,90,100,75,60,45};  
int a[]={16,25,12,30,47,11,23,36,9,18,31};
void my_shell_sort(int a[],int n);
int main()  
{  
int i;
    cout<<"Before Sort: ";  
    for( i=0; i<11; i++)  
      cout<<a[i]<<" ";  
      cout<<endl;  
my_shell_sort(a,11);return 0;
    
}  
void my_shell_sort(int a[],int n){
    int count=1;//记录第几趟结果
int d=n/2;
while(d!=0){
for(int i=0;i<d;i++){
for(int j=i+d;j=0&&(a[t]<a[t-d])){
  int temp=a[t];
a[t]=a[t-d];
a[t-d]=temp;
t=t-d;
}
}
}
d=d/2;
        cout<<"第"<<count++<<"趟结果:";
for(int j=0;j<n;j++){cout<<a[j]<<" ";}cout<<endl;
}
}

赞0 2214次