18.6 排序-快速排序

快速排序的重要性：

  • 快速排序几乎可以说是目前所有排序算法中，最快的一种排序算法。
    • 当然，没有任何一种算法是在任意情况下都是最优的。
    • 比如希尔排序确实在某些情况下可能好于快速排序。
    • 但是大多数情况下，快速排序还是比较好的选择。
  • 快速排序的重要性：
    • 如果有一天你面试的时候，让你写一个排序算法。
    • 你可以洋洋洒洒的写出多个排序算法，但是如果其中没有快速排序。
    • 那么证明你对排序算法也只是浅尝辄止，并没有深入的研究过。
    • 因为快速排序可以说是排序算法中最常见的，无论是C++的STL中，还是Java的SDK中其实都能找到它的影子。
    • 快速排序也被列为20世纪十大算法之一。
  • AnyWay，快速排序非常重要。

认识快速排序

  • 希尔排序相当于插入排序的升级版，快速排序其实是我们学过的最慢的冒泡排序的升级版。
    • 我们知道冒泡排序需要经过很多次交换，才能在一次循环中，将最大放在正确的位置。
    • 而快速排序可以在一次循环中（其实是递归调用），找出某个元素的正确位置，并且该元素之后不需要任何移动。
  • 快速排序最重要的思想是分而治之。
  • 比如我们下面有这样一堆数字需要排序：
    • 18.6 排序-快速排序 - 图1
    • 第一步：从其中选出65（其实就是其中的任意数字，我们以65举个栗子）；
    • 第二步：我们通过算法：将所有小于65的数字放在65的左边，将所有大于65的数字放在65的右边。
    • 第三步：递归的处理左边的数据，（比如你选择31来处理左侧），递归的处理右边的数据，（比如选择75来处理右侧，当然选择81可能更加合适）。
    • 最终：排序完成。
  • 和冒泡排序的不同？
    • 我们选择的65可以一次性将它放在最正确的位置，之后不需要任何移动。
    • 需要从开始位置两两比较，如果第一个就是最大值，它需要一直向后移动，直到走到最后。
    • 也就是即使已经找到了最大值，也需要不断继续移动最大值，而插入排序对数字的定位是一次性的。

快速排序的枢纽

  • 在快速排序中有一个很重要的步骤就是选取枢纽（pivot也有人称为主元）。
    • 如何选择才是最合适的枢纽呢？
  • 一种方案是直接选择第一个元素作为枢纽。
    • 但第一个作为枢纽在某些情况下，效率并不是特别高。
  • 另一种方案是使用随机：
    • 随机取pivot？但是随机函数本身就是一种消耗性能的操作。
  • 另一种比较游戏的解决方案:取头 、中、尾的中位数
    • 例如：8、12、3 的中位数就是8；

快速排序的效率：

  • 快速排序的最坏情况效率
    • 什么情况下会有最坏的效率呢？就是每次选择的枢纽都是最左边或者最后边的。
    • 那么效率等同于冒泡排序。
    • 而我们的列子可能有最坏的情况么？是不可能的，因为我们是选择三个值的中位值。
  • 快速排序的平均效率：
    • 快速排序的平均效率是O(N*logN)。
    • 虽然其它某些算法的效率也可以达到O(N*logN)，但是快速排序是最好的。