7.1 快速排序的描述

分解：数组 A[p..r]被划分为两个(可能为空)子数组 A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于 A[q]，而A[q]也小于等于A[q+1..r]中的每个元素。其中，计算下标q也是划分过程的一部分。

解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序。

合并：因为子数组都是原址排序的，所以不需要合并操作:数组A[p..r]已经有序。

下面的程序实现快速排序:

伪代码 过程 QUICKSORT
//初始调用QUICKSORT(A,1,A.length)
QUICKSORT(A,p,r)
  if p < r
    q = PARTITION(A,p,r)
    QUICKSORT(A,p,q-1)
    QUICKSORT(A,q+1,r)
伪代码 过程 PARTITION
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
PARTITION进行操作的过程

alt alt alt

7.1-1

Using figure 7.1 as a model, illustrate the operation of PARTITION on the array A=⟨13,19,9,5,12,8,7,4,21,2,6,11⟩.

使用图7.1作为模型，说明数组A=⟨13,19,9,5,12,8,7,4,21,2,6,11⟩上的分区的操作.

Solution

⟨13,19,9,5,12,8,7,4,21,2,6,11⟩

⟨13,19,9,5,12,8,7,4,21,2,6,11⟩

⟨13,19,9,5,12,8,7,4,21,2,6,11⟩

⟨9,19,13,5,12,8,7,4,21,2,6,11⟩

⟨9,5,13,19,12,8,7,4,21,2,6,11⟩

⟨9,5,13,19,12,8,7,4,21,2,6,11⟩

⟨9,5,8,19,12,13,7,4,21,2,6,11⟩

⟨9,5,8,7,12,13,19,4,21,2,6,11⟩

⟨9,5,8,7,4,13,19,12,21,2,6,11⟩

⟨9,5,8,7,4,13,19,12,21,2,6,11⟩

⟨9,5,8,7,4,2,19,12,21,13,6,11⟩

⟨9,5,8,7,4,2,6,12,21,13,19,11⟩

⟨9,5,8,7,4,2,6,11,21,13,19,12⟩

7.2 快速排序的性能

7.3 快速排序的随机化版本

7.4 快速排序分析

思考题