排序算法之快速排序

终于讲到了排序的重点了。快排即使不是排序中最经典的算法，能算上是非常出色的算法了

1. 快排简介 #

快速排序是一种基于分治技术的重要排序算法，是冒泡算法的一种改进。是由东尼.霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要O(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

2. 快排原理 #

快速排序用分治的思想，将一个整串分为两个子串。左边子串中所有的数都不会大于右边子串中的数。

步骤为：

从数组中挑选一个数作为“中轴”，（选择中轴有许多不同的策略，不过我们一般会选择数组的第一个元素）。
重新排列数组，使得所有比中轴小的元素放在中轴的左边，所有比中轴大的元素放在中轴的右边，中轴元素放在中间。当然，跟中轴相等的数放在哪边都无所谓。
按上述步骤递归执行新生成的子串。

递归的最底层是零个或者一个数，也就说是已经排好序的。

3. 时间和空间复杂度 #

我看了网上很多的数学证明，也不想多说。再说，即使用数学证明出来了，实际应用也是另一回事。我到现在也就知道快排的最好、平均和最坏的时间复杂度，而没有去纠结是怎么证明出来的（或许这样不好吧）。最好：O(nlogn), 平均:O(1.38nlogn，也就是nlogn)，最坏：O(n2)。平均情况下只比最好情况多执行38%的比较操作，不过最坏情况下就已经是平方的数量级了。

被快速排序所使用的空间，依照使用的版本而定。使用原地（in-place）分区的快速排序版本，在任何递归调用前，仅会使用固定的額外空間。然而，如果需要产生O(logn)嵌套递归调用，它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要O(log n)次的嵌套递归调用，所以它需要O(log n)的空间。最坏情况下需要O(n)次嵌套递归调用，因此需要O(n)的空间。

然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列，我们必须要记住我们的变量像是left和right，不再被认为是占据固定的空间；也需要O(log n)对原来一个n项的数列作索引。因为我们在每一个堆栈框架中都有像这些的变量，实际上快速排序在最好跟平均的情况下，需要O(log2 n)空间的比特数，以及最坏情况下O(n log n)的空间。然而，这并不会太可怕，因为如果一个数列大部份都是不同的元素，那么数列本身也会占据O(n log n)的空间字节。

非原地版本的快速排序，在它的任何递归调用前需要使用O(n)空间。在最好的情况下，它的空间仍然限制在O(n)，因为递归的每一阶中，使用与上一次所使用最多空间的一半，且2n。它的最坏情况是很恐怖的，需要O(n2)空间，远比数列本身还多。如果这些数列元素本身自己不是固定的大小，这个问题会变得更大；举例来说，如果数列元素的大部份都是不同的，每一个将会需要大约O(logn)为原来存储，导致最好情况是O(n log n)和最坏情况是O(n2 log n)的空间需求。

4. 算法 #

具体算法如下：

//交换两个数
function swap(&$x, &$y){
    $temp = $x;
    $x = $y;
    $y = $temp;
}
function partition(&$a, $left, $right){
    $p = $a[$left];
    $i = $left;
    $j = $right+1;
    do{
        //寻找大数
        do{
            $i++;
        }while($a[$i]<$p && $i<=$j);
        //寻找小数
        do{
            $j--;
        }while($a[$j]>$p && $j>=$i);
        //交换
        swap($a[$i], $a[$j]);
    }while($i<$j);
        
    swap($a[$i], $a[$j]);
    swap($a[$left], $a[$j]);
        
    return $j;
}
    
//快排,数组，左边界，右边界（数组长度）
function quickSort(&$a, $left, $right){
    if($left>=$right){
        return;
    }
    $mid = partition($a, $left, $right);
    quickSort($a, $left, $mid);
    quickSort($a, $mid+1, $right);
}

5. 快排思想 #

快排的算法很简单，而且大部分高级语言的排序库函数都是用的快排。不过我们从快排的这个分治思想中还是能够学到很多的东西的。

第一个就是在数量级很大的数中寻找第j大（小）的数，这个j一般小于等于10，比如在100万个数中找出第3小的数。我们通常的想法是用一种最快的排序算法，比如堆排序或者归并排序，将整个数组排好序之后取出第三个数。这样时间复杂度是O(nlogn)。可是如果我们用快排的思想，只需要O(n)的时间复杂度就行了。因为我们就是要的第3小的数，而不关心其他的数是第几，因此我们只需要取出下标是2（下标从0开始）数就是第三小的数了。因此，我们改进一下quickSort()函数，在返回$mid后，判断一下$mid与3的大小。如果正好等于3那么正好找到了，如果比3大，那么我们需要在后面的部分找，否则我们在前面的部分找。
在大数量级中找出前10个最小的数，这个与第一种情况是一样的，只需要检测返回的$mid值就行了，不过这个返回的是一个数组罢了。
在有n个实数组成的数组中，有正数，有负数，怎样让所有的负数都位于正数之前。这个通过快排就非常好解决了。我们自己可以认为地引入一个0，然后对数组进行一次快速排序就可以了。

好的，快排就先这样吧。