本讲内容

归并排序
快速排序

两种排序算法都是使用分治思想
分治是一种解决问题的处理思想，递归是一种编程技巧

归并排序

原理

如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序图解

代码实现

采用分治思想的算法一般通过递归实现
复习：递归怎么写？
1、分析推导出递推公式
2、找到递归终止条件
3、把递推公式翻译成代码

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解

TODO：merge_sort（）函数实现

算法分析

• 空间复杂度：O（n）
  尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。
• 时间复杂度：O（nlgn）
• 稳定排序算法

快速排序

原理

如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

代码实现

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

终止条件：
p >= r

TODO: quick_sort（）函数实现

// 快速排序，A是数组，n表示数组的大小
quick_sort(A, n) { 
quick_sort_c(A, 0, n-1)
}

// 快速排序递归函数，p,r为下标
quick_sort_c(A, p, r) {
if p >= r then 
return q = partition(A, p, r) // 获取分区点 
quick_sort_c(A, p, q-1) 
quick_sort_c(A, q+1, r)
}

算法分析

• 原地排序算法
• 不稳定排序算法
• 最好时间复杂度O（nlgn），平均 O（nlgn），最坏O（n2）

对比

归并和快排对比

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。
归并排序虽然稳定，但额外占用内存空间较大，在空间复杂度上快排更有优势，一般快排使用的多.

思考：使用快排在O（n）内找出无序数组的第K大元素