排序算法（二）
冒泡、插入和选择排序，他们的时间复杂度都是O（n^2），比较高，适合小规模数据的排序。
归并排序和快速排序的时间复杂度为O（nlogn），这两种排序算法适合大规模的数据排序，要更常用。
归并排序和快速排序都用到了分治思想，可以借鉴这个思想，来解决非排序的问题，比如：如何在O（n）的时间复杂度内找一个无序数组中的第K大元素？
归并排序的原理
如果要对一个数组进行排序，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排序好的两部分合并在一起，这样整个数组就有序了。
分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，二者并不冲突。
用递归代码来实现归并排序：
递推公式：
merge_sort(p…r) = merge(merge_sort(p…q),merge(q+1,r))
终止条件：
p >= r 不用再继续分解
归并排序的性能分析
- 归并排序是一个稳定的排序算法。
- 归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况、还是平均情况，时间复杂度都是O（nlogn）。
- 归并排序不是原地排序算法，因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间，空间复杂度是O（n）。
快速排序的原理
如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。
遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。
根据分治、递归的处理思想，我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。
归并排序中有一个merge()合并函数，快速排序中有一个partition()分区函数。该函数就是随机选择一个元素作为pivot（一般情况下，可以选择p到r区间的最后一个元素），然后对A[p…r]分区，函数返回pivot的下标。
快速排序和归并排序的区别：
归并排序的处理过程是由下到上的，先处理子问题，然后再合并。
快排的处理过程是由上到下的，先分区，然后再处理子问题。
快速排序的性能分析
- 快速排序是原地排序，空间复杂度是O（1）。
- 快速排序是不稳定的排序算法。
- 快速排序在大部分情况下的时间复杂度都可以做到O（nlogn），只有在极端情况下，才会退化到O（n^2）。