本文共 2200 字，大约阅读时间需要 7 分钟。

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

1  insertionSort(A, n, g)2      for i = g to n-13          v = A[i]4          j = i - g5          while j >= 0 && A[j] > v6              A[j+g] = A[j]7              j = j - g8              cnt++9          A[j+g] = v1011 shellSort(A, n)12     cnt = 013     m = ?14     G[] = {?, ?,..., ?}15     for i = 0 to m-116         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.

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

551432

Sample Output 1

24 1312345

Sample Input 2

3321

Sample Output 2

113123

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=1000005;int n;int a[maxn];int cnt;vector
        
          G;void InsertSort (int g){ for (int i=g;i
         
          =0&&a[loc]>temp) { a[loc+g]=a[loc]; loc-=g; cnt++; } a[loc+g]=temp; }}void ShellSort (){ int h=1; while (h<=n) { G.push_back(h); h=3*h+1; } for (int i=G.size()-1;i>=0;i--) { InsertSort(G[i]); }}int main(){ scanf("%d",&n); for (int i=0;i
          
           =0;i--) printf("%d%c",G[i],i==0? '\n':' '); printf("%d\n",cnt); for (int i=0;i
          
         
        
       
      
     
    
   

转载地址：http://tpaen.baihongyu.com/