3.快速排序

         哇偶，上节被愚弄了呢，可怕。那这一节将功补过好了给大家介绍一种比较实用的方法--快速排序。上一节所学的冒泡排序有效的解决了桶排序浪费的问题，不过算法的执行效率非常的低。他的时间复杂度达到了O（N^2）。举个栗子，听好喽。

        假设我们的计算机每秒钟可以运行10亿多次，那么对1亿个数进行排序，桶排序需要0.1秒，而冒泡排序则需要1000万秒，也就是115天。天了噜，电脑都得烧坏了。那可不可以既不用浪费空间又可以快一点的算法呢？Duang，Duang，Duang，快速排序来了。哇，听名字就觉得很快。

         接下来，我们又有些小任务了，没错和前两节一样，我们要做的就是排序。假设我们对“6，1,2,7,9,3,4，5,10,8”这10个数进行排序。==之前不是排5个，现在怎么让我排10个了，加工资吗。少废话，快干活。

        首先我们在这个序列中随便找一个数作为基准数。有多随便呢？要你管。哇，那基准数是什么鬼？别害怕，基准数就是一个参照的数而已，就和我们初中物理学的参考系一个意思。what？好吧。

        我们就把第一个数字6作为基准数吧，有意见吗？没意见没意见，惹不起惹不起。接下来我们要怎么做呢？我们需要把上述10个序列中比6大的放在6的右边，比6小的放在6的左边。那我们要怎样才能实现这个目的呢？其实方法很简单。

        我们分别从序列“6，1,2,7,9,3,4，5,10,8”的两端开始查找。先从右往左找一个小于6的数，再从左到右找一个大于6的数，然后交换他们。此时我们可以用两个变量i,j分别指向最左边和最右边。i指向6，j指向8。

        由于我们的基准数设置的是6，是最左边的数，所以j先从右往左移动。j一个一个向左移动也就是j--，直到遇到一个小于6的数停下来。接下来i再一个一个向右移动，直到遇到一个大于6的数停下来。最后j停在了5，i停在了7。然后i和j交换位置。此时交换后的序列就变成了6,1,2,5,9,3,4,,7,10，8。

        接下来j继续向左移动j--，发现了4，i继续向右移动发现了9，再进行交换，此时交换后的序列就变成了6,1,2,5,4,3,9,7,10,8

        然后j继续向右移动发现了3，i继续向左移动也遇到了3，哇，我们两个失散多年的兄妹终于相认了。此时我们将基准数6和3进行交换。交换后的序列变成了3,1,2,5,4,6,9,7,10,8

        我们总结一下刚刚的过程：其实j的任务就是找到小于基准数的数，i的任务就是要找到大于基准数的数，直到i和j相遇为止。

         现在我们可以以6为分界点拆成两个序列，左边的序列是"3 1 2 5 4"，右边的序列是"9,7,10,8"，我们用上述的方法分别处理左右两边的序列

        最终我们会得到这样的序列：1,2,3,4,5,6,7,8,9,10。

        快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。

        废话不多说了来人，上代码。威。。。武。。。

        最后到了说复杂度的时候了，快速排序的最差时间复杂度和冒泡排序的一样，都是O（N^2），它的平均时间复杂度是O（NlogN）