[数据结构与算法]Shell Sort( ALDS1_2_D)

Shell Sort is a generalization of?Insertion Sort?to arrange a list of?nn?elements?AA.

1  insertionSort(A, n, g)
2      for i = g to n-1
3          v = A[i]
4          j = i - g
5          while j >= 0 && A[j] > v
6              A[j+g] = A[j]
7              j = j - g
8              cnt++
9          A[j+g] = v
10
11 shellSort(A, n)
12     cnt = 0
13     m = ?
14     G[] = {?, ?,..., ?}
15     for i = 0 to m-1
16         insertionSort(A, n, G[i])

A function shellSort(A, n) performs a function insertionSort(A, n, g), which considers every?gg-th elements. Beginning with large values of?gg, it repeats the insertion sort with smaller?gg.

Your task is to complete the above program by filling??. Write a program which reads an integer?nn?and a sequence?AA, and prints?mm,?Gi(i=0,1,...,m?1)Gi(i=0,1,...,m?1)?in the pseudo code and the sequence?AA?in ascending order. The output of your program must meet the following requirements:

• 1≤m≤1001≤m≤100
• 0≤Gi≤n0≤Gi≤n
• cnt?does not exceed??n1.5??n1.5?

Input

In the first line, an integer?nn?is given. In the following?nn?lines,?Ai(i=0,1,...,n?1)Ai(i=0,1,...,n?1)?are given for each line.

Output

In the first line, print an integer?mm. In the second line, print?mm?integers?Gi(i=0,1,...,m?1)Gi(i=0,1,...,m?1)?separated by single space character in a line.
In the third line, print?cnt?in a line. In the following?nn?lines, print?Ai(i=0,1,...,n?1)Ai(i=0,1,...,n?1)?respectively.

This problem has multiple solutions and the judge will be performed by a special validator.

Constraints

• 1≤n≤1,000,0001≤n≤1,000,000
• 0≤Ai≤1090≤Ai≤109

Sample Input 1

5
5
1
4
3
2

Sample Output 1

2
4 1
3
1
2
3
4
5

Sample Input 2

3
3
2
1

Sample Output 2

1
1
3
1
2
3

解题思路：输出的解读（1）输出分组的次数? ?（2）每次分组的步长? （3）交换次数? ?（4）排序后的数

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e6+10;
int a[N],cnt;
vector<int> G;

void shellsort(int a[],int n){
    for(int h=1;h<=n;h=3*h+1) G.push_back(h); //存储划分的步长值
    for(int k=G.size()-1;k>=0;k--){ //取每个步长值
        int g=G[k]; //读取步长值
        for(int i=g;i<n;i++){ //插入排序
            for(int j=i;j>=g && a[j]<a[j-g];j-=g){
                swap(a[j],a[j-g]);
                cnt++;
            }
        }
    }
    return;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    shellsort(a,n);
    cout<<G.size()<<endl;  //输出分组的次数
    for(int i=G.size()-1;i>=0;i--){ //每次分组的步长
        cout<<G[i];
        if(i) cout<<" ";
    }
    cout<<endl;
    cout<<cnt<<endl;
    for(int i=0;i<n;i++) cout<<a[i]<<endl;
    return 0;
}