[关闭]
@zqbinggong 2018-04-27T08:36:36.000000Z 字数 1490 阅读 378

chap7 快速排序

快速排序 算法导论

内容


快速排序

  1. 最坏情况下运行时间为
  2. 期望运行时间是,并且内含的常数因子非常小
  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)——,因为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每次都均分数组)为,算法期望时间为
  3. 这里通过进入最小分支来减少栈深度,并不是说减少了递归的次数,事实上,递归的次数是不变的。关键在于,栈深度指的是一次计算的空间最大值,当进入小分支时,在达到if分支的底端前(p=r),TRQ不断进栈直至达到底端,之后的过程就是,先出栈一个TRQ,再进入一个TRQ,栈深度处于动态平衡中,......

7-6 对区间的模糊排序

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


代码实现

java

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注