排序算法 - 快速排序

   概要

   快速排序（Quicksort）是对冒泡排序算法的一种改进。快速排序是一种基于分而治之的排序算法。

   它的基本思想是: 选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

   基准元素的选择，以及元素的交换，都是快速排序的核心问题。    

   一、基准元素的选择

   最简单的方式是选择第1个元素。但是针对特殊情况比如原本逆序的数列，期望排列成顺序数列，整个数列并没有被分成两半。如何避免这种情况？

   解决办法：随机选择一个基准元素，并且让基准元素和数列首元素交换位置。

   二、元素的交换

   选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边，大于基准元素的都交换到基准元素的另一边。具体实现有两种方法。

   1. 双边循环法

   选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素。

   接下来进行第1次循环，从right指针开始，让指针所指向的元素和基准元素做比较，如果大于pivot，则指针向左移动。如果小于pivot，则right指针停止移动，切换到left指针。

   轮到left指针，让指针所指向的元素和基准元素做比较，如果小于等于pivot，则指针向右移动。如果大于pivot，则left指针停止移动。

   让left和right指针所指向的元素进行交换。

   接下来进入第2次循环，重新切换到right指针，向左移动。按照这个思路继续往下，

   最后，等到left指针和right指针重合的时候，将left指针所指向的元素和基准元素所在位置的元素进行交换。返回left指针所在的位置，这个就是基准元素的位置，根据基准元素，分成两部分递归排序。

   2. 单边循环法

    双边循环法从数组两边交替遍历元素，虽然更加直观，但是代码实现相对繁琐，而单边循环法则简单得多，只从数组的一边对元素进行遍历和交换。

    mark指针代表小于基准元素的区域边界。
    具体实现过程：

    从基准元素的下一个位置开始遍历数组。

    如果遍历到的元素值大于等于基准元素时，就继续往后遍历

    如果遍历到的元素小于基准元素值时，则需要做两件事：

    1）将mark指针右移1位，因为小于pivot的区域边界增大

    2）让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。

    最后，将pivot元素交换到mark指针所在位置，返回mark指针所在的位置，这个就是基准元素的位置，根据基准元素，分成两部分递归排序。这一轮宣告结束。