数据结构-怀化学院期末题

题目：

利用希尔排序算法实现线性表的排序。希尔排序是根据给定的增量序列将线性表分隔成某个“增量”的记录组成一个子序例，在子序列中采用直接插入排序完成。

输入

第一行为元素个数n(1<=n<=1000)，第二行为n个元素值(整数)，即需要排序的元素个数，第三行增量序列中增量个数m，第四行为m个增量，可以假定最后一个增量为1。

输出

对每一测试用例，用m行输出各增量进行希尔排序结果，用空格隔开。

输入样例：

10
49 38 65 97 76 13 27 49 55 4
3
5 3 1

输出样例：

13 27 49 55 4 49 38 65 97 76
13 4 49 38 27 49 55 65 97 76
4 13 27 38 49 49 55 65 76 97

代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10;int main(){int n;int a[N];int m;int b[N];cin >> n;for(int i = 0;i < n;i ++){cin >> a[i];}cin >> m;      for(int i = 0;i < m;i ++){cin >> b[i];}for(int i = 0;i < m;i ++){for(int j = b[i];j < n;j ++){int t = a[j];int k = j - b[i];while(k >= 0 && a[k] > t){a[k + b[i]] = a[k];k -= b[i];}a[k+b[i]] = t;}for(int j = 0 ;j < n;j ++)cout << a[j] << ' ';cout << endl;}return 0;
}