scau 8640 希尔(shell)排序

Description

用函数实现希尔(shell)排序，并输出每趟排序的结果,初始增量d=n/2,其后d=d/2

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

每行输出一趟排序结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

3 2 6 0 1 5 4 8 7 9
1 0 3 2 4 5 6 8 7 9
0 1 2 3 4 5 6 7 8 9

希尔排序是插入排序的一种，它从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。

希尔排序实质上采用了分组插入的方法，先将整个待排序序列分割成几组，从而减少参与直接插入排序的数据量，对每组进行分别直接插入排序，然后增加每组的数据量，重新分组。当经过几次分组排序后，整个序列“基本有序”时，再对整体序列进行一次直接插入排序。

步骤：

（1）第一趟取增量d1(d1

（2）第二趟取增量d2，同上

（3）直至dn=1(dn

Tips:这个增量d的取值也是有要求的，当然题目给了初始增量d=n/2，其后增量d=d/2

这些定义初看是比较难理解的，直接上样例好了

初始增量d1=10/2=5，分成如上五个组

首先看第一组，5大于3且5在3的前面，因此需要调换位置，序列变成3 4 8 0 9 5 2 6 7 1

再看第二组，4大于2且4在2的前面，因此需要调换位置，序列变成3 2 8 0 9 5 4 6 7 1

再看第三组，8大于6且8在6的前面，调换位置，序列变成3 2 6 0 9 5 4 8 7 1

再看第四组，0小于7且0在7的前面，无需调换位置

第五组，9大于1且9在1的前面，调换位置，序列变成3 2 6 0 1 5 4 8 7 9

第一趟排序完成，这个序列稍微有序了那么一点。

后来又想了想，按橙线这么画可能还是比较难理解，那就看看红线画的吧，当增量d=2时，会被分成两组，进行八次循环。每一次循环，每一组就会多一个数。应该好理解一点了吧……

以此类推即可。

#include 
#include 
#include 
#include 
#include 

using namespace std;

int n,a[100005];

void print()
{
    for(int i=1;i<=n;i++)
        cout << a[i] << ' ';
    cout << endl;
}

void ShellInsert(int a[],int d)
{
    for(int i=d+1;i<=n;i++)
    {
        if(a[i-d]>a[i])
        {
            int j;
            a[0]=a[i];
            for(j=i-d;j>0 && a[0]=1)
    {
        ShellInsert(a,d);
        //print();
        d=d/2;
    }
}

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> a[i];
    ShellSort(n);
    return 0;
}