给定一个长度为n的整数数组nums，要求必须使用【归并排序】的方法将该数组升序排序。
1.1 归并排序
- 分：将数组分成多个小数组，直到只有一个元素。
- 治：自底向上合并小数组（merge）
1.2 代码
将 arr [n1+n2] 数组分为两个小数组：L [n1], R [n2]
- merge算法：
- i , j , k 三个指针分别指向三个数组
一个例子
int a[] = {5, 2, 4, 7, 1, 3, 2, 6};
sort(a, 0, 7);
sort里面要合并的不仅是只有两个元素的数组，所以merge也不能直接比较大小，然后考虑交不交换。
#include<iostream>
using namespace std;void merge(int arr[], int l, int r, int mid) {int n1 = mid - l + 1; int n2 = r - mid; // 先吧arr数组的 l-mid，mid+1-r 部分拷贝到L，R数组int* L = new int[n1]; int* R = new int[n2]; for (int i = 0; i < n1; i++) {L[i] = arr[l + i];}for (int j = 0; j < n2; j++) {R[j] = arr[mid + 1 + j]; }// 再用三个指针合并L R数组，拷回到arrint i = 0, j = 0; int k = l; while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++; }while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}delete[] L;delete[] R;
}void sort(int num[], int l, int r) {if (l < r) { // 递归终止条件int mid = (l + r) / 2; sort(num, l, mid); sort(num, mid + 1, r); merge(num, l, r, mid); }
}int main() {int n;cin >> n;int num[n]; for (int i = 0; i < n; i++) {cin >> num[i];}sort(num, 0, n - 1); for (int i = 0; i < n; i++) {cout << num[i] << " ";}return 0;
}