快速排序和归并排序详解

快速排序（Quicksort）是对冒泡排序的一种改进。

基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。然后再按此方法对这其中一部分数据进行快速排序，这是递归调用。再按此方法对另一部分数据进行快速排序，这也是递归调用。

算法介绍

设要排序的数组是A[0]……A[n-1]，首先任意选取一个数据作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序算法所完成的工作：

1. 设置两个变量 i、j，排序开始的时候：i=0，j=n-1；
2. 以第一个数组元素作为关键数据，赋值给 pivot，即 pivot =A[0]；
3. 从 j 开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于 pivot 的值A[j]，将 A[j] 和 A[i] 互换（互换保证了 A[j] < A[i]，也就是保证了要趋向于前方的关键码都小于 pivot )；
4. 从 i 开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于pivot 的A[i]，将 A[i] 和 A[j] 互换（互换保证了 A[j] < A[i]，也就是保证了后方的关键码都大于 pivot ） 重复第3、4步，直到 i=j 。
5. 完成本轮比较

快速排序例子

假设待排序的序列仍为：3 2 5 9 2 。第一轮比较，选取第一个关键码 3 为pivot，初始值 i =0, j =4，整个的比较过程如下图所示：

快速排序评价

快速排序的最坏时间复杂度为 O(n^2)，这是一种退化的情况，在大多数情况下只要选取了合适的划分元后，时间复杂度为 nlog(n)，快速排序通常比其他 Ο (n log n) 算法更快，属于非稳定排序算法。

归并排序

归并排序，英文名称是MERGE-SORT。它是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

二路归并

比较 a[i] 和 b[j] 的大小，若 a[i]≤b[j]，则将第一个有序表中的元素 a[i] 复制到 r[k] 中，并令 i 和 k 分别加上1；否则将第二个有序表中的元素b[j]复制到 r[k] 中，并令 j 和 k 分别加上1；如此循环下去，直到其中一个有序表取完；然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标 t 的单元。这个过程，请见下面的例子演示。

归并算法

归并排序的算法我们通常用递归实现。先把待排序区间 [s,t] 以中点二分；接着把左边子区间排序；再把右边子区间排序；最后把左区间和右区间用一次归并操作合并成有序的区间 [s,t] 。

归并排序评价

归并排序的最坏时间复杂度为O(nlogn) ，是一种稳定排序算法。