Question
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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]) |
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
0
Meaning
题目的要求是用希尔排序给一组数据排序,除了输出排列过后的数据。还需要输出增量序列以及排序次数。题目要求使用指定的增量序列,即1,4,13,40,121等等,该增量序列也是效率极高的一个,算法的时间复杂度维持在1.25。
Solution
如果理解了插入排序的话,这题应该不难。希尔排序就是给插入排序中的增量1换成指定的数,然后进行多次插入排序(当然最后肯定需要进行一次增量1的排序,以保证数据的有序性)。或许会疑惑,这样不是时间耗得更多 吗?,其实不然,因为插入排序法可以高速处理顺序比较整齐的数据,希尔排序就是充分发挥了这一特长的高速算法!还是回到解题步骤吧:在基础的插入排序函数中带入一个参数增量g,外层套一个增量序列G,每次给g=G[i]赋值,基础的插入排序算法中稍微修改一下就ok,给之前的加1,改成加g。
Coding
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#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]); } |
Summary
希尔排序,我在之前写代码时候在更改后的插入排序函数中原本是给i直接赋值给j,然后去判断a[j-1]和当前值tmp的大小,但是题目中前几个可以ac,后面就不可以了,喜欢深究的小伙伴可以告诉我这是为什么。
原来的:
1 2 3 4 5 6 7 8 9 10 11 |
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; } } |
修改后:
1 2 3 4 5 6 7 8 9 10 11 |
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; } } |
入坑笔记:大数组需要定义在main函数外面!
希尔排序和插入排序的比较:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#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; } |