算法导论-快速排序

Introduction to Algorithms (third edition)

第七章：Quicksort

快速排序是分治思想的绝妙运用，提出至今，在基于比较的排序算法中，无人出其右。快排是排序算法中最重要的一种，C++库中的排序算法就是快排的变种。快排的平均时间复杂度是O(nlg(n))，最坏情况下快排的时间复杂度是O(n²)，但由于隐藏的常数项很小，所以往往是排序算法的首选，因此必须彻底理解熟练掌握。

书中给出的分割数组方法如 PARTITION 所示。将数组的最后一个元素A[r]作为参考，从左到右扫描，每次将碰到比A[r]小的元素与最左边的比A[r]大的元素交换，最后，将A[r]与最左边的比A[r]大的元素交换，从而整个数组被分为3个部分。

PARTITION(A, p, r)
1    x = A[r]
2    i = p - 1
3    for j = p to r-1
4        if A[j] <= x
5            i = i + 1
6            swap(A[i], A[j])
7    swap(A[i+1], A[r])
8    return i+1

另外一种常见的分割方法如 PARTITION-2 所示。这种分割方法左右同时扫描，只有赋值操作，没有元素的交换操作，因此一般情况下减少了元素的复制拷贝等操作，但同时增加了比较语句。需要特别注意边界条件，否则容易出错。（暂时我还没看出下面代码中的bug，如果你发现了，请务必告诉我！）

PARTITION-2(A, p, r)
01    x = A[p]
02    i = p
03    j = r
04    while i < j
05        while i < j and A[j] >= x
06            j = j - 1
07        if i < j
08            A[i] = A[j]
09            i = i + 1
10        while i < j and A[i] <= x
11            i = i + 1
12        if i < j
13            A[j] = A[i]
14            j = j - 1
15    A[i] = x
16    return i

一般的快排代码如下所示。如果数组是有序的，那么每次分割就将数组分成0, 1, n-1三部分，相当于冒泡排序，时间复杂度是O(n²)。为了解决这个问题，可以修改参考元素的选择方法，比如随机选择，或者选择3个元素，选取中间值。通过这些修改，可以改善快排在一般情况下的最坏情况时间复杂度。为什么要说一般情况下呢，因为仍然可以通过修改输入使得针对特定修改下的快排算法，其时间复杂度是O(n²)。

QUICKSORT(A, p, r)
1    if p < r
2        q = PARTITION(A, p, r)
3        QUICKSORT(A, p, q-1)
4        QUICKSORT(A, q+1, r)

Exercises

7.1-2 PARTITION 中的第4行条件永远满足，因此i一直增加到r-2，最后返回r-1；检测这种特殊情况……

7.1-3 遍历n个数，每个数上操作都是常数级别，因此复杂度是O(n)

7.1-4 change the <= in 4th line of PARTITION to >=

7.2-1 T(n) = T(n-1) + O(n) = T(n-2) + O(n-1) + O(n) = ... = O(1 + 2 + ... + n) = O(n2)

7.2-2 O(n2)

7.2-3 same like 7.2-2

7.2-4 对于基本有序的数组，插入排序只需要很少的比较次数，而快速排序则会产生较差的分割，因而导致较差的复杂度

7.2-5 对于最小的情况，每次都是走α分支，假设第m层结束，只有一个节点，因此有nαm = 1，解得m = -lg(n) / lg(α)；对于最大的情况，每次都走1-α分支

Problems
7-4 Stack depth for quicksort
a. 显然的
b. 每次都是最坏情况下的分割 0, 1, n-1或者n-1, 1, 0
c. 每次先对分割中小的数组排序，代码如下

QUICKSORT''(A, p, r)
1    while p < r    // partition and sort the smaller subarray first
2        q = PARTITION(A, p, r)
3        if q-p < r-q
4            QUICKSORT''(A, p, q-1)
5            p = q + 1
6        else
7            QUICKSORT''(A, q+1, r)
8            r = q -1