Shell排序?Shell排序是大量数据需要排序时，更为高效的插入排序。它的算法思想基于插入排序的算法思想流程：（1）将n个元素数组分成n/2个数字序列，第一个数据和第n/2个数据为一对，等等，以此类推（2）一次循环...
Shell排序
?
Shell排序是大量数据需要排序时，更为高效的插入排序。它的算法思想基于插入排序的算法思想
流程：
（1）将n个元素数组分成n/2个数字序列，第一个数据和第n/2个数据为一对，等等，以此类推
（2）一次循环使每一个数对排列好顺序
（3）变成n/4个数对，再次排序。
（4）不断重复上述过程，随着序列减少直至最后变为1个，完成排序。
具体如何怎么排的可以运行代码查看每一步排序。
?
?
#include<iostream>
#include<cstdlib>
#include<ctime>
using?namespace?std;
void?ShellSort(int?*a,int?len)
{
????int?x,t,j;
????for?(int?r?=?len/2;?r?>=1?;?r/=2)????//外层循环分组
????{
????????for?(int?i?=?r;?i?<?len;?i++)????
????????{//内层循环设置一定间距r，分别比较对应元素，当r=1时，这个时候就为插入排序，数组元素数量大时这时效率比插入排序高。
????????????t=a[i];
????????????j=i-r;
????????????while?(j>=0&&t<a[j])
????????????{
????????????????a[j+r]=a[j];
????????????????j-=r;
????????????}
????????????a[j+r]=t;
????????????x++;
????????????cout<<"Sort?result?after?"<<x<<"?step";??????????????//输出每一步排序结果
????????????for?(int?k?=?0;?k?<?len;?k++)?cout<<a[k]<<"?";
????????????cout<<endl;
????????}
????????
????}
????
}
int?main()
{
????srand(time(NULL));
????int?n;
????cout<<"Please?cin?the?size?of?array:"<<endl;?//输入数组的大小
????cin>>n;
????int?a[n];
????cout<<"Array?before?sorting:"<<endl;
????for?(int?i?=?0;?i?<?n;?i++)????????????//利用随机数作为数组输入
????{
????????a[i]=rand()/1000;
????????cout<<a[i]<<"?";
????}
????cout<<endl;
????ShellSort(a,10);
????cout<<"Array?after?sorting:"<<endl;??//输出排序后的数组
????for?(int?i?=?0;?i?<?10;?i++)?cout<<a[i]<<"?";
????cout<<endl;
????return?0;?
????
}
