首页 > 代码库 > ACM:归并排序,以及利用归并排序思想求解逆序对数!
ACM:归并排序,以及利用归并排序思想求解逆序对数!
(一)归并排序
分析:
(1)划分问题:把序列分成元素个数尽量相等的两半。
(2)递归求解:把两半元素分别排序。
(3)合并问题:把两个有序表合并成一个。(每次只需要把两个序列的最小元素加以比较,删除其中的较小元素并加入合并后的新表)
#include <iostream> using namespace std; const int MAXN = 1000; int A[MAXN], T[MAXN]; void merge_sort(int *A, int x, int y, int *T) { if(y - x > 1) { int m = x + (y - x) / 2; //划分 int p = x, q = m, i = x; merge_sort(A, x, m, T); //递归求解 merge_sort(A, m, y, T); //递归求解 while(p < m || q < y) { if(q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++]; //从左半数组复制到临时空间 else T[i++] = A[q++]; //从右半数组复制到临时空间 } for(i = x; i < y; ++i) A[i] = T[i]; //从辅助空间复制回A数组 } } int main() { int n; cin >> n; for(int i = 0; i < n; ++i) cin >> A[i]; merge_sort(A, 0, n, T); for(int i = 0; i < n; ++i) cout << A[i] << endl; return 0; }上述代码中的两个条件是关键!
首先,只要有一个序列非空,就要继续合并while(p < m || q < y)。
其次对于:if(q >= y || (p < m && A[p] <= A[q]))。
(1)如果第二个序列为空,这个时候第一个序列肯定非空,不然就不能进入while循环,这个时候复制A[p]。
(2)否则(第二个序列非空),当且仅当第一个序列也非空,且A[p] <= A[q]时,才复制A[p]。
(二)利用归并排序思想求解逆序对数
题目:给一列数,求它的逆序对数!
分析,由于n可能很大,所以O(n2)的枚举方法肯定超时。所以要用分治的方法!
(1)划分问题:把序列分成元素个数尽量相等的两半。
(2)递归求解:统计i和j均在左边或者均在右边的逆序对个数。
(3)合并问题:统计i在左边,j在右边的逆序对个数。
划分以后,对于右边的每个j,统计左边比它大的元素个数f(j),则所有f(j)之和便是答案。
所以由于我们的归并排序操作是从小到大进行的,当右边的A[j]复制到T中时,左边还没有来得及复制到T的那些数就是左边所有比A[j]大的数。
所以此时在累加器中加上左边元素个数m-p就可以了!
#include <iostream> using namespace std; const int MAXN = 1000; int A[MAXN], T[MAXN]; void inverse_pair(int *A, int x, int y, int* cnt, int *T) { if(y - x > 1) { int m = x + (y - x) / 2; //划分 int p = x, q = m, i = x; inverse_pair(A, x, m, cnt, T); //递归求解 inverse_pair(A, m, y, cnt, T); //递归求解 while(p < m || q < y) { if(q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++]; //从左半数组复制到临时空间 else { T[i++] = A[q++]; //从右半数组复制到临时空间 *cnt += m-p; //更新累加器 } } for(i = x; i < y; ++i) A[i] = T[i]; //从辅助空间复制回A数组 } } int main() { int n; cin >> n; for(int i = 0; i < n; ++i) cin >> A[i]; int cnt = 0; inverse_pair(A, 0, n, &cnt, T); cout << cnt << endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。