首页 > 代码库 > 归并排序以及逆序数计算
归并排序以及逆序数计算
hi,主要注意两点:
1、如果只用一份传入的临时数组,在merge的最后,要把所有元素,copy回原数组;
2、逆序数计算的时候 low2-i,而不是 low2-low1
其实还可以做一点优化,就是在merge函数里,后半段如果没结束,可以不用copy到临时数组,
然后从临时数组,copy回原数组的时候,可以少copy一段。
#include <iostream> using namespace std; int reverse_num = 0; template<class T> void print(T a[], int n) { for (int i=0; i<n; i++) { cout << a[i] << " "; } cout << endl; } void merge (int a[], int start, int mid, int end, int c[]) { int low1 = start; int low2 = mid+1; int i = start; while (low1 <= mid && low2 <= end) { if (a[low1] > a[low2]) { c[i] = a[low2]; reverse_num += (low2-i); low2++; } else { c[i] = a[low1]; low1++; } i++; } for (;low1 <= mid; low1++) { c[i] = a[low1]; i++; } for (;low2 <= end; low2++) { c[i] = a[low2]; i++; } for (int i=start; i<=end; i++) { a[i] = c[i]; } } void merge_sort (int a[], int start, int end, int c[]) { if (start >= end) { return; } int mid = (start + end)/2; merge_sort(a, start, mid, c); merge_sort(a, mid+1, end, c); merge(a, start, mid, end, c); } int main () { int a[] = {3,4,1,20,18,31,6,13}; int size = sizeof(a)/sizeof(int); cout << size << endl; int c[size]; print(a, size); merge_sort(a, 0, size-1, c); print(a, size); cout << "reverse_num:" << reverse_num << endl; }
本文出自 “天眼神童的新家” 博客,请务必保留此出处http://tianyanshentong.blog.51cto.com/3356396/1559580
归并排序以及逆序数计算
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。