分治策略之快速排序算法的实现

一、导论

    快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。这就是分而治之的思想，因此，快速排序算法也是分治策略的一种应用。

二、快速排序的大致思想

    快速排序实现的重点在于数组的拆分。

    首先选择列表中的一个元素作为基准元素【通常我们将数组的第一个元素定义为比较元素】，其他的元素都与这个元素做比较，找出小于这个基准值的值、大于基准值的值。这称为“分区”，包括：

    （1）一个由所有小于基准值的数字组成的子数组

    （2）基准值

    （3）一个由所有大于基准值的数组组成的子数组

分区

    然后再将“小于v”和“大于v”的数据块作为子数组，同样选择基准值，再进行上述类似操作，分别对这两个子数组进行分区。当执行到数据块中只有1个元素或者0个元素时，即完成排序。

    这个问题中的基线条件是执行到数据块中只有1个或者0个元素。

三、例子演示

数组arr

    将该数组从小到大排序。

    首先选取数组第一个数23为基准数，存入temp变量中，从数组的左右两边界向中间进行遍历，定义两个指针 i 和 j，i 最开始指向数组的第一个元素，j 最开始指向数组的最后一个元素。指针 i 从左向右移动，指针 j 从右向左移动。先移动 j 指针（从右忘左移），当 j 指向的数大于基准数时，略过，j 继续往左移动，直到遇到小于等于基准数的数arr[j]，将arr[j]填入arr[i]中；再移动 i 指针，当 i 指向的数小于等于基准数时，略过，i 继续往右移动，直到遇到不比基准数小的数arr[i]，将arr[i]填入arr[j]中；再移动 i 指针，再移动 j 指针...(轮换移动)，直到 i 和 j 指针相遇，此时将temp（基准数）填入arr[i]中即完成算法的第2个步骤。接下来分别将基准数左边和右边的数组按照以上方法进行聚合，直到每个子集只有一个元素，即排序完成。

    【下列图中，颜色为黄色的表明该位置为下一个被赋值的位置，也就是一个坑，等待下一次的填充。橘黄色的表示该位置刚完成值的拷贝。】

    将数组第一个数23赋给temp变量，指针 i 指向数组第一个元素，指针 j 指向数组最后一个元素。

    从j开始遍历（从右往左），遇到13时，因为13<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为13。

    再从i遍历（从左往右），遇到45时，因为45>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为45。

    继续从j遍历，遇到11时，因为11<=temp，因此将arr[j]填入arr[i]中，即此时指针 i指向的数为11。

    从i遍历，遇到89时，因为89>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为89。

    从j遍历，遇到17时，因为17<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为17。

    从i遍历，遇到72时，因为72>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为72。

    从j遍历，遇到3时，因为3<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为3。

    从i遍历，遇到26时，因为26>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为26。

    从j遍历，和 i 重合，将temp（基准数23）填入arr[i]中。

    第一轮排序完成，紧接着递归，将23左边和右边的子区间分别用以上方法进行排序，直到区间只有一个元素即排序完成。

四、代码截图

快排算法

五、算法时间复杂度分析

    快速排序的性能高度依赖于你选择的基准值。

    1、最佳情况：算法复杂度O(n log n)

    快速排序最优的情况就是每一次取到的元素都刚好平分整个数组。

    此时的时间复杂度公式则为：T(n) = 2T(n/2) + f(n)；

    T(n/2)为平分后的子数组的时间复杂度，f(n) 为平分这个数组时所花的时间；在最佳情况下，栈长为O(log n)，每一层运行时间为O(n)。

    由主定理法可以得到：T(n)=O(nlogn)

    假设总是将中间的元素用作基准值，在这种情况下，调用栈如下：

最佳情况下调用栈

    调用栈短得多！因为每次都将数组分成两半，所以不需要那么多递归调用。很快就到达了基线条件，因此调用栈短得多。通过上图也能发现，整个算法需要的时间为O(n) * O(log n) = O(n log n)。

    2、最糟情况：算法复杂度O(n^2)

    当待排序的序列为正序或逆序排列时，且每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。

最坏情况调用栈

    此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为：

    最终其时间复杂度为O(n^2)。

    【换个说法：在最糟情况下，栈长为O(n)，在调用栈的每层都涉及O(n)个元素，完成每层所需的时间都为O(n)。因此整个算法需要的时间为O(n) * O(n) = O(n^2)】。

    3、平均情况：算法复杂度O(n log n)

    最佳情况也是平均情况。只要每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(nlogn)。快速排序是最快的排序算法之一，也是D&C典范。