787. 归并排序 - AcWing题库

前面我们有对快速排序和快速选择进行讲解，他们的 平均时间复杂度 为 O(nlogn)

当然，也存在一个最坏的情况

最好的情况就是

所以，其实快速排序的时间复杂度可能会根据你输入的数据而变化，并不 稳定

那么存在一种算法能稳定的有O(nlogn)吗？

当然有，这就是我们要讲的 归并排序

代码模板

#includeusing namespace std;const int N = 1e6 + 8;
int n ;
int q[N] , temp[N];void merge_sort(int q[] , int l, int r){if( l >= r ) return ;int mid = (l + r  ) / 2;merge_sort(q , l , mid);merge_sort(q , mid +  1, r);int i = l , j = mid + 1, k = 0 ;while(i <= mid && j <= r ){if(q[i] <= q[j]){temp[k ++] = q[i ++];}else{temp[k ++] = q[ j ++];}}while(i <= mid) temp[k ++] = q[i ++];while(j <= r) temp[k ++] = q[j ++];for(int i = l , j = 0 ; i <= r ; i ++ , j ++){q[i] = temp[j];}}int main(){scanf("%d" , &n);for(int i = 0 ; i < n ; i ++){scanf("%d" , &q[i]);}merge_sort(q , 0 , n - 1);for(int i = 0 ; i < n ; i ++){printf("%d " , q[i] );}return 0;
}

算法思路

在快速排序算法中，排序思路是找到一个数x，将所有小于x的放在左边，所有大于x的放在右边。

其中比较麻烦的就是如何找到x，通常有以下方法

• 最左值——q[left]
• 中间值——q[（left + right）/ 2]
• 最右值——q[right]

但是在归并排序中的思路就 另辟蹊径 了，直接默认对半分

首先进行 递归排序 ， 让左右侧都是 有序的序列

然后在创建一个 辅助数组 ，在两侧分别选择对应的值放入数组

图示演示

假设当前我已经通过 递归 ，将 左右两边的数据都排序好了得到下图

仅会保证分别有序

现在分别设置两个指针指向左侧序列（i） 和 右侧序列（j）

开始判断

	if(q[i] <= q[j]){temp[k ++] = q[i ++];}else{temp[k ++] = q[ j ++];}

默认情况下的话，相等时会移动左侧的指针

• q[i] = 2
• q[j] = 1

q[i] > q[j]，填入temp数组，并前移j指针

然后在对比当前的i指针和j指针的值

• q[i] = 2
• q[j] = 3

q[i] <= q[j]，填入temp数组，前移i指针

一直排序，直到i <= mid或者 j <= r中间某一个条件出现。

当然，这里演示的是最简单的两个数组刚好切分，还有其他的情况，比如

• 左侧的数组长
• 右侧的数组长

所以需要继续循环，将后续的值全部放入

解释一下为什么可以直接放入

因为既然right已经到最右边了，但是left还没有到最右边

证明当前的left值 都会大于 right的值，所以就可以直接放入了（left左边的数都会比right最右边的大）