常用算法模板 | 归并排序
为信竞同学整理的常用算法模板
1void merge_sort(int q[], int l, int r){
2 //如果只有一个元素，则递归终止
3 if (l == r) return;
4
5 //选取中点，将数组二分
6 int mid = l + r >> 1;
7 //将左侧数组排序
8 merge_sort(q, l, mid);
9 //将右侧数组排序
10 merge_sort(q, mid + 1, r);
11
12 //i，j双指针
13 int k = l, i = l, j = mid + 1;
14 //归并数组
15 while (i <= mid && j <= r){
16 //“<=”保证稳定排序
17 if (q[i] <= q[j]) tmp[k++] = q[i++];
18 else tmp[k++] = q[j++];
19 }
20
21 //左侧还有剩余元素
22 while (i <= mid) tmp[k++] = q[i++];
23 //右侧还有剩余元素
24 while (j <= r) tmp[k++] = q[j++];
25
26 for (int i = l;i <= r; i++) q[i] = tmp[i];
27}
时间复杂度：O(nlogn)
空间复杂度：O(N)，需要一个与原数组相同长度的数组做辅助
稳定性：归并排序是稳定的排序算法