归并排序详解

归并排序详解

分治法在每层递归时都有三个步骤：

1.分解原问题为若干个子问题，这些子问题是原问题规模较小的实例；

2.解决子问题，递归求解各子问题，如果子问题规模足够小，则直接求解；

3.合并子问题得到原问题的解。

归并排序完全遵循分治法：

1.分解待排序的n个元素的序列，分成各具有n/2个元素的两个子序列；

2.使用归并排序递归地排序两个子序列；

3.合并两个已排序的子序列得到已排序的答案。

当待排序的子序列只有一个元素时，递归开始“回升”，这种情况下不要做任何工作，因为长度为1的每个序列都已经排好。

#include using namespace std;//注意区间状况是[left, mid], (mid, right];void merge_test(int* a, int left, int mid, int right) { int i, j; int n1 = mid - left + 1; int n2 = right - mid; //建立新数组L[n1 + 1], R[n2 + 1]; int L[n1 + 1], R[n2 + 1]; for (i = 0; i < n1; i++) { L[i] = a[left + i]; } for (i = 0; i < n2; i++) { R[i] = a[mid + i + 1]; } L[n1] = 0x3f3f3f3f, R[n2] = 0x3f3f3f3f;//设为无穷大可不必考虑数组为空的情况 //合并, 从小到大 i = j = 0; for (int k = left; k <= right; k++) { if (L[i] <= R[j]) { a[k] = L[i++]; } else { a[k] = R[j++]; } }}//区间为[left, right];void merge_sort(int* a, int left, int right) { if (left < right) {//当left = right时区间内只有一个元素,不进行递归; int mid = (left + right)/2; merge_sort(a, left, mid); merge_sort(a, mid + 1, right); merge_test(a, left, mid, right); }}int main(){ int n; while (cin >> n) { int a[n]; for (int i = 0; i < n; i++) { cin >> a[i]; } //归并排序，从小到大 merge_sort(a, 0, n - 1);//注意用闭区间 //测试 int flag = 0; for (int i = 0; i < n; i++) { if (flag++) cout << " "; cout << a[i]; } cout << endl; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。