1089 Insert or Merge (25分)

原题链接

插入还是归并

本题分析归并排序思路递归写法非递归写法

本题分析

分析：插入/归并排序 都可以用sort来解决

归并排序

思路

每次都是从头排到尾 只是每次步长step不同

递归写法

void merge(int A[], int L1, int R1, int L2, int R2) { int i = L1, j =L2, index = 0; while(i < R1 && j < R2) { if(A[i] <= B[j]) { C[index++] = A[i]; } if(A[i] >= B[j]) { C[index++] = B[j]; } } while(i < R1) { C[index++] = A[i++]; } while(j < R2) { C[index++] = B[j++]; } for(i = 0; i < index; i++) { A[L1 + i] = temp[i]; //合并后的序列赋值回数组A } } void mergeSort(int A[], int left, int right) { if(left < right) { int mid = (left + right) / 2; mergeSort(A, left, mid); mergeSort(A, mid+1, right); merge(A, left, mid, mid + 1, right); } }

非递归写法

void mergeSort(int A[], int left, int right) { if(left < right) { int mid = (left + right) / 2; mergeSort(A, left, mid); mergeSort(A, mid+1, right); merge(A, left, mid, mid + 1, right); } } void mergeSort(int A[]) { for(int step = 2; step / 2 <=n; step *= 2) { for(int i = 1; i <= n; i += step) { int mid = i + step / 2 -1; if(mid + 1 <= n) { merge(A, i, mid, mid + 1, min(i + step - 1, n)); } } } } //如果只在乎每次排序的结果 可以用sort来替代 void mergeSort(int A[]) { for(int step = 2; step / 2 <= n; step *= 2) { for(int i = 1; i <= n; i += step) { sort(A + i, A + min(i + step, n + 1)); } } }

AC代码

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 110; int n; int origin[maxn], temp[maxn], changed[maxn]; //原始序列 复制临时序列 排序数列 void showarray(int origin[]) { for(int i = 1; i <= n; i++) { cout << origin[i]; if( i < n) cout << " "; } } bool issame(int A[], int B[]) { for(int i = 1; i <= n; i++) { if(A[i] != B[i]) { return false; } } return true; } int k; //记录已排序的最后一个位置 bool InsertSort() { bool flag = false; for(int i = 2; i <= n; i++) { sort(origin + 1, origin + i + 1); if(!flag && issame(origin, changed)) { flag = true; k = i; break; } } sort(origin + 1, origin + k + 2); if(flag) return true; else return false; } void mergeSort(int (&A)[maxn]) //其实每次都是从头排到尾只不过是步长不一样 { int sstep,j;//记录步长 for(int step = 2; step / 2 <= n; step *= 2) { for(int i = 1; i <= n; i += step)//对每组进行排序 { sort(A + i, A + min(i + step, n + 1)); } if(issame(A, changed)) { j = step; break; } } sstep = j * 2; for(int i = 1; i <= n; i += sstep)//对每组进行排序 { sort(A + i, A + min(i + sstep, n + 1)); } } int main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> origin[i]; temp[i] = origin[i]; } for(int i = 1; i <= n; i++) { cin >> changed[i]; } if(InsertSort()) { cout << "Insertion Sort" << endl; showarray(origin); } else { cout << "Merge Sort" << endl; mergeSort(temp); showarray(temp); } return 0; }