shell排序

任务描述
本关任务：实现shell排序算法，void ShellSort(int R[],int N,int d[],int t)。

相关知识
基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整，它是由Donald.L.Shell在1959年提出来的。

所谓“宏观”调整，指的是，“跳跃式”的插入排序。    即：将记录序列分成若干子序列，每个子序列分别进行插入排序。关键是，这种子序列不是由相邻的记录构成的。

Donald.L.Shell设计的排序算法，特点：
    (1)  缩小增量
    (2)  多遍插入排序

例如，选用增量序列(4， 2，1)3个增量，进行3遍插入排序

案例：

#include <iostream>
#include <stdio.h>
using namespace std;
#define Max 500    /*N为数据量大小*/

void ShellSort(int R[], int N, int d[], int t);
void Print(int R[], int N);

int main()
{
    int *R, N, i, *d, t;
    cin >> N;
    R = new int[N + 1];
    for (i = 1; i <= N; i++)
        cin >> R[i];
    Print(R, N);
    cin >> t;
    d = new int[t];
    for (i = 0; i < t; i++)
        cin >> d[i];
    ShellSort(R, N, d, t);
    Print(R, N);
    return 0;
}

void Print(int R[], int N)
{
    int i;
    cout << R[1];
    for (i = 2; i <= N; i++)
        cout << "," << R[i];
    cout << endl;
}

void ShellSort(int R[], int N, int d[], int t)
{
    for (int k = 0; k < t; k++) { // 对于每个增量
        int dk = d[k];
        for (int i = dk + 1; i <= N; i++) { // 将R[i]插入到所在分组的有序序列中
            if (R[i] < R[i - dk]) {
                int j = i - dk;
                int temp = R[i];
                while (j > 0 && temp < R[j]) { // 移动元素
                    R[j + dk] = R[j];
                    j -= dk;
                }
                R[j + dk] = temp; // 插入元素
            }
        }
        Print(R, N); // 输出中间状态
    }
}