chap7 快速排序

快速排序 算法导论

内容

快速排序

1. 最坏情况下运行时间为$\Theta(n ^2)$
2. 期望运行时间是$\Theta(n\lg n)$，并且内含的常数因子非常小
3. 能进行原址排序
4. 使用了分治思想（这是必然的，算法要想节省时间必然直接或者间接用到分治思想，因为只能通过减少重复计算来节约算法层面上的时间。例如堆排序就是间接的，因为它所使用的堆已通过减少重复计算节约了时间）
5. 备注，这里算法是原址的，而归并排序中不是原址的。原因在于，归并排序中，分解的两个子数组是各自排好序的，两者没有关联，因而在合并时，如果不用第三方数组，则会有大量的交换操作；而这里，两个子数组之间是有关联的，且这种关联满足了排序的要求，也就不需要再合并了。规模上来看，两者复杂度相当，这也是必然的，因为它虽然没有合并操作，但是它在让两个子数组产生关联上付出了代价。

QuickSort(A,p,r)

if p < r
    q = Partition(A,p,r)
    QuickSort(A,p,q-1)
    QuickSort(A,q+1,r)

Partition(A,p,r)——$\Theta(n)$，因为for循环会执行n-1次

x = A[r]
i = p - 1 # i 用来记录某个位置，该位置之后的数，要么比x大，要么for循环还没到它;之前的数一定不大于x
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

Randomized-Partition(A,p,r)

i = Random(p,r)
exchange A[r] with A[i]
retrun Partition(A,p,r)

习题中的算法

7-2 针对相同元素的快速排序

版本1（存在问题，可能会有相同的元素被划分到左边的子数组）
Partition(A,p,r)

i = j = Partition(A,p,r)
while i > 1 and A[i-1] = A[i]
    i = i - 1
while j < r and A[j+1] = A[j]
    j = j + 1
return i,j

版本2
Partition(A,p,r)

x = A[p]
i = h = p #i到h的位置都是与x相同的数
#找到小于x的数，将该数和A[h+1]以及A[i]三者做互换j->i,h+1->j,i->h+1
for j = p+1 to r
    if A[j] < x
        y = A[j]
        A[j] = A[h+1]
        A[h+1] = A[i]
        A[i] = y
        i = i + 1
        h = h + 1
    else if A[j] = x
        exchange A[h+1] with A[j]
        h = h + 1
retrun i,h

7-4 快速排序的栈深度，尾递归

Tail-Recursive-Quicksort(A,p,r)

while(p < r)
    q = Partition(A,p,r)
    #进入较小的子数组，以减少栈深度
    if q-p < r-q
        TRQ(A,p,q-1)
        p = q + 1
    else 
        TRQ(A,q+1,r)
        r = q - 1

1. 栈深度：一次计算中会用到的栈空间的最大值
2. 此处栈深度最坏情况下（partition每次都均分数组）为$\Theta(\lg n)$，算法期望时间为$O(n \lg n)$
3. 这里通过进入最小分支来减少栈深度，并不是说减少了递归的次数，事实上，递归的次数是不变的。关键在于，栈深度指的是一次计算的空间最大值，当进入小分支时，在达到if分支的底端前(p=r)，TRQ不断进栈直至达到底端，之后的过程就是，先出栈一个TRQ，再进入一个TRQ，栈深度处于动态平衡中，......

7-6 对区间的模糊排序

基本思路：利用7-2中的算法，定义区间的大小关系，随机选取一个区间，将比他小的往左放，大的往右边放，相等的（重叠的）放在中。代码

代码实现

java