简介

刷leetcode碰到一个难题,里面用到了分治法,想到了归并排序,觉得以前学的排序基本忘得差不多了,特别是快排,直接sort()调用,自己基本实现不了,索性重新复习一遍

归并排序

简介

归并排序(Merging Sort)就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并,2-路归并最为简单和常用。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

算法思想

假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度是1,然后两两归并,得到[n/2]个长度为2或1的有序子序列;再两两归并,…如此重复,直到得到一个长度为n的有序子序列为止。

用途

1.排序:归并排序的时间复杂度是O(nlog2n),当有n个记录时,需要进行log2n次归并排序,每一次归并,关键字比较次数不超过n,元素移动次数都是n,因此是nlog2n。
归并排序是稳定排序(在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的),可以用于链式结构。
2.找逆序对数,以前打ACM碰到过好几次,第一次见到这种题觉得好难,这就说明对归并排序理解不深,这点在紫书上也提到过。当然也可以通过树状数组解决这类问题。

代码+解释

归并排序
对于这张图,将原序列分解为n个子序列,然后开始比较归并,对于分解可以用二分+递归来实现,合并也是一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//算法实现
//采用紫书代码
void merge_sort(int* A, int x, int y, int* T) {
if(y - x > 1) {
int m = x + (y - x) / 2; //划分
int p = x, q = m, i = x;
merge_sort(A, x, m, T); //递归求解
merge_sort(A, m, y, T); //递归求解
while(p < m || q < y) {
if(q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++]; //从左半数组复制到临时空间
else T[i++] = A[q++]; //从右半数组复制到临时空间
    // else T[i++] = A[q++], cnt += m - p; //这一行就可以实现求逆序对数的问题,其中cnt要先清零
}
for(i = x; i < y; i++) A[i] = T[i]; //从辅助空间复制回A数组
}
}

最后更新: 2018年09月19日 22:13

原始链接: https://xdong.me/2018/09/18/排序算法总结/

× 请我吃糖~
打赏二维码