快速排序的重要性
快速排序几乎可以说是目前所有排序算法中，最快的一种排序算法
当然，没有任何一种算法是在任意情况下都是最优的.比如希尔排序确实在某些情况下可能好于快速排序.但是，大多数情况下，快速排序还是比较好的选择
快速排序的重要性
因为快速排序可以说是排序算法中最常见的，无论是C++的STL中，还是java的SDK中其实都能找到它的影子.快速排序也被列为20世纪十大算法之一
快速排序的认识
希尔排序相当于插入排序的升级版，快速排序其实是我们学习过的最慢的冒泡排序的升级版
我们知道冒泡排序需要经过很多次交换，才能在依次循环中，将最大值放在正确的位置。而快速排序可以在一次循环中(其实是递归调用)，找出某个元素的正确位置，并且该元素之后不需要任何移动
快速排序最重要的思想是分而治之
比如我们下面有这样一些数字需要排序：
第一步：从其中选出65(其实可以是选出任意的数字，我们以65举个例子)
第二步：我们通过算法，将所有小于65的数字放在65左边，将所有大于65放在右边
第三步：递归处理左边的数据(比如你选择31来处理左侧),递归的的处理右边的数据
最终：排序完成
和冒泡排序不同的是什么？
我们选择的65可以一次性将它放在最正确的位置，之后不需要移动
需要从开始位置两个两个比较，如果第一个就是最大值，它需要一直向后移动，直到走到最后
也就是即使已经找到了最大值，也需要不断继续移动最大值。而快速排序对数字的定位是一次性的
快速排序的枢纽
在快速排序中有一个很重要的步骤就是选取枢纽（pivot也有人称为主元）
如何选择才是最合适的枢纽呢？
- 一种方案是选择第一个元素作为枢纽:但第一个枢纽在某些情况下，效率不是特别高
- 另一种方案是选择一个随机数:随机取pivot？但是随机函数本身就是一个耗性能的操作
- 另一种方案是比较优秀的解决方案：取头、中、尾的中位数..例如： 8 12 3的中位数就是8
快速排序的效率
快速排序的最坏情况效率
什么情况下会有最坏的效率？就是每次选择的枢纽都是最左边或者最后边的
那么效率等同于冒泡排序
而我们的例子可能有最坏的情况吗？不可能的，因为我们是选择三个值的中位值
快速排序的平均效率
快速排序的平均效率是O(N*logN)
虽然其他某些算法的效率也可以达到O(N*logN),但是快速排序是最好的