打卡Day10
学习内容 : 排序（下）：如何用快排思想在O(n)内查找第K大元素？
1.归并排序的原理和性能分析
归并排序使用的就是分治思想，分治是一种解决问题的处理思想，递归是一种编程技巧
归并排序的时间复杂度也是 O(nlogn)
2.快速排序的原理和性能分析
快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
归并和快排的区别
归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。
快排的时间复杂度也是 O(nlogn)
小结：
归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。
本文参考【极客时间】专栏《数据结构与算法之美》。
