快速排序本身不难,对于初学者,难就难在递归的理解。

算法步骤:

  1. 选取主元(以下选取数组开头为主元);
  2. 小于等于主元的放左边,大于等于主元的放右边;
  3. 分别对左边,右边递归,即重复 1,2 步。
void QuickSort(int array[], int left, int right)
{
    int i = left;
    int j = right;
    int base = array[left];

    while (i <= j)
    {
        while (array[i] < base)
            i++;
        while (array[j] > base)
            j--;

        if (i <= j)
        {
            swap(array[i], array[j]);
            i++;
            j--;
        }
    };

    if (left < j)
        QuickSort(array, left, j);
    if (i < right)
        QuickSort(array, i, right);
}

算法复杂度

最好的情况,每次我们运行一次分区,我们会把一个数组分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数组。则会有关系式:

$$ T(n)=2T(\frac n2)+O(n) $$

解出 $T_{best}(n)=O(nlogn)$。

最坏的情况,在分割后,两子数组总是拥有各为 1 和 n-1 长度的数组,则递归关系式变为:

$$ T(n)=T(n-1)+O(n)+O(1)=T(n-1)+O(n) $$

解出 $T_{worst}(n)=O(n^2)$。

细节讨论

(1):如何选择主元

本文的代码很简单,以数组首元素作为主元。但我们知道主元的大小直接决定快排的效率,因为数组的划分需要依靠主元,理想状态下,给定的主元正好可以把数组分为长度相等的两个子数组,但找到并确定这样的主元还需要耗费额外的时间,如此一来,得不偿失。

因此现实生活中,我们更多的采取 "三点中值",即数组首元素,尾元素和中间元素这三个元素的中位数作为主元。

(2):等于主元的数如何放置

左右扫描,如果遇到和主元相等的元素怎么办?是暂停扫描(然后交换)还是继续扫描?

首先,两个方向采取的策略应该是一样的,也就是要么都暂停(然后交换),要么都继续扫描。否则将导致两个子数组不平衡。

其次,为了更好分析这个问题,我们不妨考虑所有元素都相同的情形。如果我们遇到和主元相等的时候不停止,那么从左到右扫描时,两指针将相遇,此次过程结束。结果呢?什么都没做,却得到了两个大小极其不均衡的数组。算法时间复杂度为 $O(n^2)$。如果我们选择遇到相等元素时停止扫描,然后交换,那么虽然看上去交换的次数变多了,但是我们将得到大小相等(或者差 1)的两个子数组,算法的时间复杂度为 $O(nlogn)$。

因此,遇到和主元相等的元素时候我们都暂停扫描,交换元素后继续,直到指针相遇或者交叉。(摘自深入解析快速排序

(3):i <= j 的等号可以去掉么

不可以!

我们先来看下代码的结尾,

if (left < j)
    QuickSort(array, left, j);
if (i < right)
    QuickSort(array, i, right);

从上面的代码可以看出,当 while 循环结束,i 需指向左子数组的尾元素,j 需指向右子数组的首元素,但两者不能重合,因为一旦重合,子数组的递归就可能会打乱它们的排序。

(4):分割划分策略

本文所采用的划分策略很简单,易于理解,实际应用中,要复杂的多,有兴趣的朋友可以参见这里

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2019-10-09
原文链接:https://ethsonliu.com/2019/10/quick-sort.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。