归并排序之确定递归层数

本文主要是介绍归并排序之确定递归层数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定一维int型数组a[0,1,…,n-1], 使用归并排序方法, 对其进行从小到大排序, 请输出递归过程中自顶自下第三层的排序结果, 其中最顶层为第一层, 即最终的排序结果层.
归并排序划分请按a[0,mid=(0+n-1)/2], a[(0+n-1)/2+1, n-1]进行划分子问题.

Input

输入第1行有一个int型正整数m (m<100), 表示有m行输入.
每行输入的第一个数为int型正整数n (8<n<1000), 后面接着输入n个int型整数.

Output

输出m行, 每行为排好序的输出.

Sample Input

2
9 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1 0

Sample Output

7 8 9 5 6 3 4 1 2
7 8 9 5 6 2 3 4 0 1

代码实现：

#include<iostream>
#include<vector>
using namespace std;// 将两个子数组合并成一个有序数组
void merge(vector<int> &arr,int left,int mid,int right){// 两个数组的长度int len1 = mid-left+1, len2 = right-mid;vector<int> a(len1),b(len2);// 对两个数组分别赋值for(int i = 0;i<len1;i++){a[i] = arr[left+i];} for(int i = 0;i<len2;i++){b[i] = arr[mid+1+i];}// 对两个数组进行比较，结果放入arr数组int i = 0,j = 0,k = left;while(i<len1 && j<len2){if(a[i]<=b[j]){arr[k++] = a[i++];}else {arr[k++] = b[j++];}}// 其中一个数组没还遍历完，直接拷贝到arr数组后面while(i<len1){arr[k++] = a[i++];}while(j<len2){arr[k++] = b[j++];}
}// 归并排序
void mergeSort(vector<int> &arr, int left, int right,int depth){if(left<right){int mid = left+(right-left)/2;// 分别对左右两半进行排序mergeSort(arr,left,mid,depth+1);mergeSort(arr,mid+1,right,depth+1);// 归并if(depth>=3){merge(arr,left,mid,right);}}
}int main(){int m;//cout<< "请输入m, 表示m行:";cin >> m;cin.ignore();vector<vector<int> > res;for(int i = 0;i<m;i++){// 输入元素个数int n;cin >> n;// 输入n个元素vector<int> arr(n);for(int i = 0;i<n;i++){cin >> arr[i];}// 输入完元素之后，进行排序mergeSort(arr,0,n-1,1);res.push_back(arr);}// 打印for(int i = 0;i<m;i++){for(int j = 0;j<res[i].size();j++){cout << res[i][j] << " ";}cout<< endl;}return 0;
}