归并排序

介绍

归并排序是一种复杂度O($nlog(n)$)的排序算法，并且在任何情况下都是，但是它不是原地算法，即需要额外存储空间

其原理是，先将区间均匀分成左右两半，然后再对左右两半继续二分，直到一个数为一个区间为止。

然后从小区间到大区间进行左右区间合并。合并方式就是将两个有序间合并为一个大区间，并且大区间保持有序，因为最小区间单元是一个数，因此最初的区间一定有序，由下至上就可以保证合并过程中的区间都是有序的。

因此可以发现，归并排序的核心是先递归后排序。

核心思想：

合并过程步骤：

• 开辟一个新的内存空间tmp用于存放合并后的区间
• 设定两个指针分别指向待合并的两个区间起点
• 比较两个指针的数，取较小值放入tmp
• 最后将未指向终点的指针所代表那个区间接到tmp区间的后面
• 将tmp区间的内容覆盖回原区间

即将两个小区间通过双指针算法，合并为一个大区间，最后把大区间的内容覆盖回原来两个小区间。

模板代码：

int q[N], tmp[N];void merge_sort(int q[N], int l, int r)
{if( l >= r) return;int mid = l + r >> 1;merge_sort(q, l, mid), merge_sort(q, mid + 1, r);int i = l, j = mid + 1, k = 0; // i 和 j 分别是左右区间的第一个下标// 区间合并while( i <= mid && j <= r ){if( q[i] < q[j] )  tmp[k++] = q[i++];else tmp[k++] = q[j++];}// 将剩余的区间补上while(i <= mid) tmp[k++] = q[i++];while(j <= r) tmp[k++] = q[j++];// 将排序好的内容重新放回q数组for(int i=l, k=0; i<=r; i++, k++) q[i] = tmp[k];
}

例题

思路：

按上述模板进行书写即可

代码：

#include<iostream>
using namespace std;const int N = 1e6 + 10;int n;
int q[N];void quick_sort(int q[N], int l, int r)
{if(l >= r) return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while(i < j){do i++;while(q[i] < x);do j--;while(q[j] > x);if( i < j ) swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j+1, r);
}int main()
{scanf("%d", &n);for(int i=0; i<n; i++) scanf("%d", &q[i]);quick_sort(q, 0, n-1);1. List itemfor(int i=0; i<n; i++) printf("%d ", q[i]);
}