MENU

排序(2):快速排序

June 3, 2018 • 文章

系列文章目录

排序(1):直接插入排序,二分查找插入排序,希尔排序
排序(2):快速排序
排序(3):堆排序
排序(4):归并排序
排序(5):基数排序
排序(6):总结

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

算法步骤:

  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):分割划分策略

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

Archives QR Code Tip
QR Code for this page
Tipping QR Code