o(nlogn)的归并排序和快速排序

这两个排序算法都要用到递归的代码，在使用递归的时候最重要的不要陷进每一环的重复中。抓住终止条件，在一个个的往上排，直至排到最后。

归并排序：就是将两组已经排序好的数组，归并为一个排序好的数组。

通俗的讲:归并排序有点像冒泡排序，不同的是，刚开始时它们都是两个先比较，而渐渐的成倍的增加比较个数。不过占内存，空间复杂度是o(n）。像是冒泡+递归。

但现实中，很少有两个已经排序好的数组。我们可以用分治思想把一混乱的数组分为子问题在合并。参考文章

image image

示意图

image

示意图

快速排序:就是取一组数据的最后一个元素，然后确定这个元素在整个数组中的位置，做法就是设置一个变量等于start，遍历一次，把大于这个数据的值都按顺序从start开始存放，直到遍历完之后，就可以找到这个元素的位置。

求第k大的数，或前k大的数都是用快排来解决，且时间复杂度为O(n)。

归并和快排的区别；

归并是先分区在计算，快排是先计算位置再分区。