您的位置: 首页  >  文章  >  第7章 快速排序

第7章 快速排序

分类: 文章 • 2025-07-16 13:04:52

7.1 快速排序的描述

7.1-1

PARTITION在数组A=<13，19，9，5，12，8，7，4，21，2，6，11>上的操作过程。

第7章 快速排序

7.1-2

当数组A[p..r]中的元素都相同时，PARTITION返回的q值是r。修改PARTITION，使得当数组A[p..r]中所有元素的值都相同时，第7章 快速排序。

PARTITION(A, p, r)
    x = A[r]
    i = p - 1
    n = 0
    for j = p to r-1
        if A[j] ≤ x
            if A[j] == x
                n = n + 1
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i+1] with A[r]
    return i + 1 - ⌈n/2⌉

7.1-3

证明：因为在规模为n的子数组上，PARTITION需要迭代n次，每次迭代的时间复杂度为第7章 快速排序，所以PARTITION的时间复杂度为第7章 快速排序。

7.1-4

修改QUICKSORT，使得它能够以非递增序进行排序。

PARTITION(A, p, r)
    x = A[r]
    i = p - 1
    for j = p to r-1
        if A[j] ≥ x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i+1] with A[r]
    return i + 1

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

7.2 快速排序的性能

7.2-1

令第7章 快速排序，对某两个恰当选出的常数第7章 快速排序，假定第7章 快速排序对所有正数第7章 快速排序都成立，特别是对于m=n-1，有第7章 快速排序。将其代入递归式，得到第7章 快速排序第7章 快速排序。其中，只要第7章 快速排序，最后一步都会成立。所以递归式第7章 快速排序。

7.2-2

当数组A的所有元素都具有相同值时，QUICKSORT的时间复杂度是第7章 快速排序。

7.2-3

证明：当数组A包含的元素不同，并且是按降序排列的时候，QUICKSORT的每一次递归调用划分产生的两个子问题分别包含了n-1个元素和0个元素，这也是QUICKSORT的最坏情况，根据7.2节开头的论述，此时QUICKSORT的时间复杂度是第7章 快速排序。

7.2-4

证明：当输入序列越有序，INSERTION-SORT的性能越优，QUICKSORT的性能越劣，当输入数组已经完全有序时，插入排序的时间复杂度为第7章 快速排序，快速排序的时间复杂度为第7章 快速排序。所以在一个对几乎有序的输入序列进行排序的问题上，INSERTION-SORT的性能往往要优于QUICKSORT。

7.2-5

证明：假设叶结点的最小深度是第7章 快速排序，最大深度是第7章 快速排序。则第7章 快速排序，第7章 快速排序。所以，在相应的递归树中，叶结点的最小深度大约是第7章 快速排序，最大深度是第7章 快速排序。

7.3 快速排序的随机化版本

7.3-1

因为随机化算法引入了随机性，从而使得算法对于所有的输入都能获得较好的期望性能。所以我们分析随机化算法的期望运行时间，而不是其最坏运行时间。

7.3-2

在RANDOMIZED-QUICKSORT的运行过程中，在最坏情况下，随机数生成器RANDOM被调用了第7章 快速排序次，在最好情况下，随机数生成器RANDOM被调用了第7章 快速排序。

7.4 快速排序分析

7.4.1 最坏情况分析

7.4.2 期望运行时间

7.4-1

证明：令第7章 快速排序，对某个恰当选出的常数c>0，假定第7章 快速排序对所有正数m<n都成立，特别是对于第7章 快速排序，有第7章 快速排序，第7章 快速排序。将其代入递归式，得到第7章 快速排序第7章 快速排序第7章 快速排序。其中，只要第7章 快速排序，最后一步都会成立。所以递归式第7章 快速排序。

7.4-2

证明：在最好情况下，快速排序每次调用PARTITION时都将数组划分成相等的两个部分，此时第7章 快速排序。运用4.5节的主方法求得：第7章 快速排序，所以快速排序的运行时间为第7章 快速排序。

7.4-3

证明：第7章 快速排序第7章 快速排序，此一元二次函数的对称轴为第7章 快速排序，所以当q=0或q=n-1时，第7章 快速排序取得最大值。

7.4-4

证明：第7章 快速排序第7章 快速排序，所以RANDOMIZED-QUICKSORT期望运行时间是第7章 快速排序。

7.4-5

证明：当对数组调用快速排序直至子数组的长度小于k时，共调用了第7章 快速排序次迭代调用，时间复杂度为第7章 快速排序。当上层的快速排序调用返回后，对整个数组运行插入排序时，因为下标为i的元素肯定小于下标为i+k的元素，所以插入排序的内层循环每次最多迭代k轮，外层循环固定迭代n轮，时间复杂度为第7章 快速排序。因此，这一排序算法的期望时间复杂度为第7章 快速排序。

从理论角度说明该如何选择k：第7章 快速排序，这样的k不可能存在。在加入常数系数的情况下进行分析：第7章 快速排序，可见k的取值取决于插入排序和快速排序的时间复杂度常熟系数的相对大小，这个需要实践才能得出结论。

思考题

7-1

a.说明HOARE-PARTITION在数组A=<13，19，9，5，12，8，7，4，11，2，6，21>上的操作过程，并说明在每一次执行第4~13行while循环时数组元素的值和辅助变量的值。

第7章 快速排序

b.证明：因为i单调递增，j单调递减，下标小于i的数组元素都小于x，下标大于j的数组元素都大于等于x，当j单调递减时不会小于i，当i单调递增时不会大于j+1，又因为子数组A[p..r]至少包含来2个元素，所以下标i和j可以使我们不会访问在子数组A[p..r]以外的数组A的元素。

c.证明：根据上一问的证明过程，当HOARE-PARTITION结束时，第7章 快速排序且i=j+1，所以第7章 快速排序。

d.证明：先定义循环不变式：在开始第4~13行while循环的每次迭代时，A[p..i-1]中的每个元素都小于或等于A[j+1..r]中的元素。证明如下：

初始化：在循环的第一次迭代之前，有i=p-1，j=r+1。此时A[p..i-1]和A[j+1..r]中都没有元素，循环不变式成立。

保持：每次循环时j先单调递减直至第7章 快速排序也即下标大于j的数组元素都大于等于x，i再单调递增直至第7章 快速排序也即下标小于i的数组元素都小于等于x，此时A[p..i-1]中的每个元素都小于或等于A[j+1..r]中的元素。

终止：终止时i=j+1，根据循环不变式，A[p..j]中的每一个元素都小于或等于A[j+1..r]中的元素。

e.利用HOARE-PARTITION，重写QUICKSORT算法。

HOARE-PARTITION(A, p, r)
    x = A[p]
    i = p - 1
    j = r + 1
    while TRUE
        repeat
            j = j - 1
        until A[j] ≤ x
        repeat
            i = i + 1
        until A[i] ≥ x
        if i < j
            exchange A[i] with A[j]
        else return j

QUICKSORT(A, p, r)
    if p < r
        q = HOARE-PARTITION(A, p, r)
        QUICKSORT(A, p, q)
        QUICKSORT(A, q+1, r)

7-2

a.如果所有输入元素的值都相同，那么随机化快速排序的运行时间会是第7章 快速排序。

b.修改PARTITION代码来构造一个新的PARTITION'(A，p，r)，它排列A[p..r]的元素，返回值是两个数组下标q和t，其中第7章 快速排序，且有

  • A[q..t]中的所有元素都相等。
  • A[p..q-1]中的每个元素都小于A[q]。
  • A[t+1..r]中的每个元素都大于A[q]。

与PARTITION类似，新构造的PARTITION'的时间复杂度是第7章 快速排序。

PARTITION'(A, p, r)
    x = A[r]
    q = p - 1
    for j = p to r-1
        if A[j] < x
            q = q + 1
            exchange A[q] with A[j]
    t = q
    for j = q+1 to r-1
        if A[j] == x
            t = t + 1
            exchange A[t] with A[j]
    exchange A[t+1] with A[r]
    return q+1, t+1

c.将RANDOMIZED-PARTITION过程改为调用PARTITION'，并重新命名为RANDOMIZED-PARTITION'。修改RANDOMIZED-QUICKSORT的代码构造一个新的RANDOMIZED-QUICKSORT'(A，p，r)，它调用RANDOMIZED-PARTITION'，并且只有分区内的元素互不相同的时候才做递归调用。

RANDOMIZED-PARTITION'(A, p, r)
    i = RANDOM(p, r)
    exchange A[r] with A[i]
    return PARTITION'(A, p, r)

RANDOMIZED-QUICKSORT'(A, p, r)
    if p < r
        q, t = RANDOMIZED-PARTITION'(A, p, r)
        RANDOMIZED-QUICKSORT'(A, p, q-1)
        RANDOMIZED-QUICKSORT'(A, t+1, r)

d.在7.4.2节中的分析方法中，假设每个元素的值是互异的，因此，一旦一个满足第7章 快速排序的主元x被选择后，就知道第7章 快速排序和第7章 快速排序以后再也不可能被比较了。另一种情况，如果第7章 快速排序在第7章 快速排序中的所有其他元素之前被选为主元，那么第7章 快速排序就将与第7章 快速排序中除了它自身以外的所有元素进行比较。类似地，如果第7章 快速排序在第7章 快速排序中其他元素之前被选为主元，那么第7章 快速排序将与第7章 快速排序中除自身以外的所有元素进行比较。

在QUICKSORT'中，一旦一个主元x被选择后，所有与x相等的元素在经历过一轮比较后将不再参与比较，其余分析不变。

7-3

a.证明：给定一个大小为n的数组，PARTITION过程等可能地选择一个元素作为主元，共有n个元素，所以任何特定元素被选为主元的概率为1/n。第7章 快速排序{第i小的元素被选为主元}=1/n。

b.证明：因为指示器随机变量第7章 快速排序=I{第i小的元素被选为主元}，所以当第q小的元素被选为主元时，第7章 快速排序。即时间复杂度为第7章 快速排序的PARTITION过程返回后，第q小的元素被选为主元，数组被分成长度分别为q-1和n-q的两个数组，所以第7章 快速排序。因此，第7章 快速排序。

c.证明：第7章 快速排序第7章 快速排序第7章 快速排序。

d.证明：第7章 快速排序第7章 快速排序第7章 快速排序第7章 快速排序第7章 快速排序。

e.证明：令第7章 快速排序，对于某个恰当选出的正常数a，假定第7章 快速排序对于所有正数q<n都成立。将其代入递归式，得到第7章 快速排序第7章 快速排序。其中，只要第7章 快速排序，最后一步都会成立。所以公式(7.6)中的递归式有解第7章 快速排序。

7-4

a.证明：在调用PARTITION后，TAIL-RECURSIVE-QUICKSORT(A，1，A.length)先是递归调用了左边的子数组，再把p的值设为右边的子数组的起始下标，此时下标p和r表示的是右边的子数组，然后重新开始循环，直至PARTITION划分的右边的子数组不存在，此时数组已经全部有序。所以，TAIL-RECURSIVE-QUICKSORT(A，1，A.length)能正确地对数组A进行排序。

b.当一个包含n个元素的数组已经有序时，针对此数组的TAIL-RECURSIVE-QUICKSORT的栈深度是第7章 快速排序。

c.修改TAIL-RECURSIVE-QUICKSORT的代码，使其最坏情况下栈深度是第7章 快速排序，并且能够保持第7章 快速排序的期望时间复杂度。

TAIL-RECURSIVE-QUICKSORT(A, p, r)
    while p < r
        // Partition and sort larger subarray.
        q = PARTITION(A, p, r)
        if 2q > p + r
            TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
            p = q + 1
        else TAIL-RECURSIVE-QUICKSORT(A, q+1, r)
            r = q - 1

7-5

a.第7章 快速排序。

b.在平凡实现中，选择第7章 快速排序（即A[1..n]的中位数）的值作为主元的概率为1/n。在三数取中法实现中，选择第7章 快速排序（即A[1..n]的中位数）的值作为主元的概率为第7章 快速排序，与平凡实现相比，此概率增加了第7章 快速排序。假设第7章 快速排序，这一概率的极限值为第7章 快速排序。

c.如果定义一个“好”划分意味着主元选择第7章 快速排序，其中第7章 快速排序。在平凡实现中，得到一个好划分的概率为第7章 快速排序。在三数取中法实现中，得到一个好划分的概率为第7章 快速排序第7章 快速排序第7章 快速排序，与平凡实现相比，这种实现中得到一个好划分的概率增加了第7章 快速排序。

d.证明：根据7.2节对快速排序的性能的探讨得出的结论，只要划分是是常数比例的，算法的运行时间总是第7章 快速排序。三数取中法只是增加了得到一个好划分的概率，所以对快速排序而言，三数取中法只影响其时间复杂度第7章 快速排序的常数项因子。

7-6

a.为n个形如第7章 快速排序的闭区间，其中第7章 快速排序，实现这些区间的模糊排序，即对j=1，2，...，n，生成一个区间的排列第7章 快速排序，且存在第7章 快速排序，满足第7章 快速排序。设计一个随机算法，具有算法的一般结构，它可以对左边端点（即第7章 快速排序的值）进行快速排序，同时它也能利用区间的重叠性质来改善时间性能。（当区间重叠越来越多的时候，区间的模糊排序问题会变得越来越容易。算法能充分利用这一重叠性质。）

FUZZ-RANDOMIZED-PARTITION(A, B, I, p, r)
    i = RANDOM(p, r)
    exchange I[r] with I[i]
    left = A[I[r]]
    right = B[I[r]]
    // Find an intersection of the pivot and other intervals
    for j = p to r-1
        if left ≤ B[I[j]] and right ≥ A[I[j]]
            left = max(left, A[I[j]])
            right = min(right, B[I[j]])
    // Partition before the intersection
    q = p - 1
    for j = p to r-1
        if B[I[j]] < left
            q = q + 1
            exchange I[q] with I[j]
    // Partition equal the intersection
    t = q
    for j = t+1 to r-1
        if left ≤ B[I[j]] and right ≥ A[I[j]]
            t = t + 1
            exchange I[t] with I[j]
    exchange I[t+1] with I[r]
    return q+1, t+1

FUZZ-RANDOMIZED-QUICKSORT(A, B, I, p, r)
    if p < r
        q, t = FUZZ-RANDOMIZED-PARTITION(A, B, I, p, r)
        FUZZ-RANDOMIZED-QUICKSORT(A, B, I, p, q-1)
        FUZZ-RANDOMIZED-QUICKSORT(A, B, I, t+1, r)

b.证明：算法中FUZZ-RANDOMIZED-PARTITION过程的时间复杂度为第7章 快速排序，在一般情况下，算法需要递归调用第7章 快速排序次，所以算法的期望运行时间为第7章 快速排序。但是，当所有的区间都有重叠的时候，算法调用一次就结束，所以算法的期望运行时间为第7章 快速排序。

相关推荐