Shell排序 C&&C++
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;
}