之前说的，冒泡排序、插入排序、选择排序三种算法的时间复杂度都是O(n^2)，很高，适用于小规模数据的排序。
而，归并排序和快速排序，适用于大规模的数据排序，更为常用。
问题
归并排序和快速排序都用到了分治思想，借助这个思想可以解决非排序问题。
如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素？
归并排序
核心思想
对于要排序的数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起。
归并排序用到的就是分治思想，顾名思义，就是分而治之，将大问题分解为小的子问题来解决。
分治思想跟递归很向。分治算法一般都用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。
如何用递归代码实现归并排序？
先写出归并排序的递推公式
递推公式：
merge_sort(p...q) = merge(merge_sort(p...r), merge_sort(r+1...q)) #r = (p+q)/2,即数组的中间位置
终止条件：
p >= q #不用再继续分解的时候
代码
def merge_sort(lt):
if len(lt) <= 1:
return lt
middle = len(lt)/2
left = merge_sort(lt[:middle])
right = merge_sort(lt[middle:])
return merge(left, right)
def merge(arr1, arr2):
arr_result = []
while len(arr1)>0 and len(arr2)>0:
if arr1[0] <= arr2[0]:
arr_result.append(arr1.pop(0))
else:
arr_result.append(arr2.pop(0))
#while循环结束，说明有个条件不满足，即有个数组已经没有数据元素了，此时将另一个数组的数据加入到结果数组中
arr_result += arr1
arr_result += arr2
return arr_result
分析
1 . 归并排序是否是稳定排序算法？关键看merge()函数，即两个有序子数组合并成最终结果数组的那部分代码。在合并过程中，如果arr1[p...r]和arr2[r+1...q]之间有相同元素，那么可以先把arr1[p...r]中的元素放入最终结果数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是稳定的排序算法。
2 . 时间复杂度分析。归并排序涉及递归，时间复杂度该如何分析？
递归适用场景：一个问题A可以分解为多个子问题B、C，求解A就就分解为求解B、C。问题B、C解决后，在把这个问题的结果合成A的结果。
若定义求解问题A的时间为T(A)，求解问题B、C的时间分别为T(B)和T(C)，则有一个递推关系
T(A) = T(B) + T(C) + K 其中K为两个子问题B、C的结果合成问题A的结果所花费时间
套用这个公式来分析归并排序的时间复杂度：
假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：
T(1) = C; n=1 时，只需要常量级的执行时间
T(n) = T(n/2) *2 + n; n>1
进一步分解可知道：
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......
= 2^k * T(n/2^k) + k * n
......
即 T(n) = 2^k * T(n/2^k) + k * n, 当 T(n/2^k) = 1 时，k = log2^n
则 T(n) = 2^log2^n + log2^n * n = Cn + n*log2^n
用大O标记法表示，T(n) = O(nlogn)
归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。
3 . 空间复杂度分析。归并排序的时间复杂度在任何情况下都是 O(nlogn)，看起来非常优秀，但是它并没有像快排那样应用广泛，其原因就是因为它有一个致命弱点，归并排序不是原地排序算法。主要原因在于merge()函数，需要借助额外的存储空间。
分析递归代码的空间复杂度并不能像时间复杂度那样累加。尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。
快速排序
核心思想
如果要排序数组中下标从 p 到 q 之间的一组数据，我们选择 p 到 q 之间的任意一个数据作为 pivot（分区点）（可选择末尾数字）。
遍历 p 到 q 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 q 之间的数据就被分成了三个部分，前面 p 到 r-1 之间都是小于 pivot 的，中间是 pivot，后面的 r+1 到 q 之间是大于 pivot 的。
其中一次排序步骤如下：
递归排序下标从 p 到 r-1 之间的数据和下标从 r+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。
递推公式
quick_sort(p...q) = quick_sort(p...r-1) + quick_sort(r+1...q)
终止条件
p >= q
代码
partition() 函数不需要额外的内存空间，保证快排是原地排序算法。
def quick_sort(lt, lindex, rindex):
if lindex < rindex:
pivot = partition(lt, lindex, rindex)
quick_sort(lt, lindex, pivot)
quick_sort(lt, pivot+1, rindex)
else:
return
def partition(lt, lindex, rindex):
i = lindex - 1
for j in range(lindex, rindex):
if lt[j] <= lt[rindex]: #最后一个数据为pivot
i += 1
lt[i],lt[j] = lt[j], lt[i]
lt[i+1], lt[rindex] = lt[rindex], lt[i+1] #将分区点交换到数组中间位置
return i
分析
1 . 快速排序是原地排序算法，即空间复杂度为O(1)。但在分区的过程涉及交换操作，如果数组中有两个相同的元素，在经过一次分区操作后，元素的相对先后顺序会改变。所以，快排不是一个稳定的排序算法。
2 . 时间复杂度分析。快排也是基于递归思想，前面的递归公式在这里仍适用。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，快排的时间复杂度也是 O(nlogn)。但是，公式成立的前提是每次分区操作，选择的 pivot 都很合适，正好能将大区间对等地一分为二。但实际上这种情况是很难实现的。如果以最后一个元素作为pivot，需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n^2)。
以上两种情况分别对应于最好情况和最坏情况，在大部分情况下快排的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化到 O(n^2)。而且，有方法将这个极端情况的概率降到很低。
快速排序和归并排序的区别
快排和归并都用到分治思想，地推公式和递归代码也相似，它们的区别在于：归并排序的处理过程是由下到上的，先处理子问题，然后再合并；而快排正好相反，它的处理过程是由上到下的，先分区，再处理子问题。
归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
解答开篇
利用分区思想，在O(n)时间复杂度时间内求无序数组中的第 K 大元素。
选择数组arr[0,n-1]的最后一个元素作为pivot，对数组arr[0,n-1]原地分区，数组分成三部分，arr[0...p-1], arr[p], arr[p+1...n-1]。如果 p+1=K，那 arr[p] 就是要求解的元素；如果 K>p+1, 说明第 K 大元素出现在 arr[p+1…n-1] 区间，再按照上面的思路递归地在 arr[p+1…n-1] 这个区间内查找。同理，如果 K<p+1，那就在 arr[0…p-1] 区间查找。
为什么上述解决思路的时间复杂度是 O(n)？
第一次分区查找，需要对大小为 n 的数组执行分区操作，需要遍历 n 个元素。第二次分区查找，只需要对大小为 n/2 的数组执行分区操作，需要遍历 n/2 个元素。依次类推，分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.…… 直到区间缩小为 1。
把每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+…+1 。这是一个等比数列求和，最后的和等于 2n-1。所以，上述解决思路的时间复杂度就为 O(n)。
另一种思路
每次取数组中的最小值，将其移动到数组的最前面，然后在剩下的数组中继续找最小值，以此类推，执行 K 次，找到的数据就是第 K 大元素。
思路是对的，但时间复杂度就不是 O(n) 了，而是 O(K * n)。当 K 是比较小的常量时，比如 1、2，那最好时间复杂度确实是 O(n)；但当 K 等于 n/2 或者 n 时，这种最坏情况下的时间复杂度就是 O(n^2) 了。