排序算法总结

简介

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

归并排序

简介

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

算法思想

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

用途

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

代码＋解释

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

//算法实现
//采用紫书代码
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数组
    }
}