Shell Sort

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])

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
 
long long cnt; //记录希尔排序次数值，可以和插入排序比较
vector<int> G;//希尔排序中的增量序列1，4，13，40，121，...
int n, a[1000005]; //入坑：大数组定义在main外部 
 
void insertSort2(int a[], int n, int g) {
	int i, j, tmp;
	for (i = g; i < n; i++) {
		tmp = a[i];
		for (j = i-g; j >=0 && a[j] > tmp; j = j - g) {
			a[j+g] = a[j];
			cnt++;
		}
		a[j+g] = tmp;
	}
}
//void insertionSort(int a[] , int n , int g){
//	for(int i =g ;i<n;i++){
//		int v = a[i];
//		int j=i-g;
//		while(j>=0&&a[j]>v){
//			a[j+g]=a[j];
//			j-=g;
//			cnt++;
//		}
//		a[j+g]=v;
//	}
//}
void shellSort(int a[], int n) {
	for (int h = 1;;) {
		if (h > n)break;
		G.push_back(h);
		h = 3 * h + 1; //这种增序列算法效率基本维持在O(N1.25)
	}
	for (int i = G.size() - 1; i >= 0; i--) {  //按逆序列指定G[i]=g
		insertSort2(a, n, G[i]);
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
//		cin >> a[i];
		scanf("%d",&a[i]);
	shellSort(a, n);
	cout << G.size() << endl;
	for (int i = G.size() - 1; i >= 0; i--) {
		printf("%d", G[i]);
		if (i)printf(" ");
	}
	cout << endl;
	cout << cnt << endl;
	for (int i = 0; i < n; i++)
		printf("%d\n", a[i]);
}

void insertSort2(int a[], int n, int g) {
	int i, j, tmp;
	for (i = g; i < n; i++) {
		tmp = a[i];
		for (j = i; j > 0 && a[j - g] > tmp; j = j - g) {
			a[j] = a[j - g];
			cnt++;
		}
		a[j] = tmp;
	}
}

void insertSort2(int a[], int n, int g) {
	int i, j, tmp;
	for (i = g; i < n; i++) {
		tmp = a[i];
		for (j = i-g; j >=0 && a[j] > tmp; j = j - g) {
			a[j+g] = a[j];
			cnt++;
		}
		a[j+g] = tmp;
	}
}

#include<iostream>
#include<vector>
using namespace std;
 
long long cnt; //记录希尔排序次数值，可以和插入排序比较
long long cnp;//记录直接插入排序次数值
vector<int> G;//希尔排序中的增量序列1，4，13，40，121，...
 
void insertSort(int a[] , int n) {
	int i, j, tmp;
	for (i = 1; i < n; i++) {
		tmp = a[i];
		for (j = i; j > 0 && a[j - 1] > tmp; j--) {
			a[j] = a[j - 1];
			cnp++;
		}
		a[j] = tmp;
	}
 
}
void insertSort2(int a[] ,int n,int g) {
	int i, j, tmp;
	for (i = g; i < n; i++) {
		tmp = a[i];
		for (j = i; j > 0 && a[j - g] > tmp; j=j-g) {
			a[j] = a[j - g];
			cnt++;
		}
		a[j] = tmp;
	}
}
void shellSort(int a[] ,int n ) {
	for (int h = 1;;) {
		if (h > n)break;
		G.push_back(h);
		h = 3 * h + 1; //这种增序列算法效率基本维持在O(N1.25)
	}
	for (int i = G.size() - 1; i >= 0; i--) {  //按逆序列指定G[i]=g
		insertSort2(a, n, G[i]);
	}
}
void print(int a[], int n) {
	int i;
	for (i = 0; i < n; i++) {
		if (i > 0)cout << " ";
		cout << a[i];
	}
	cout << endl;
}
int main() {
	int a[12] = { 3,23,4,24,567,5,8,90,7,564,12,7 };
	int b[12] = { 3,23,4,24,567,5,8,90,7,564,12,7 };
	insertSort(a, 12);
	shellSort(b, 12);
	print(a, 12);
	cout << "直接插入排序次数：" << cnp << endl;
	print(b, 12);
	cout << "希尔插入排序次数:" << cnt << endl;
	
}