快速排序

快速排序首先末尾的数作为主元,然后让大于主元的数排在前面,小于主元的数排在后面:

image.png

图中选择4作为主元,p-i之间是小于主元的数,i-j之间是大于主元的数,排序过程增加j,若A[j]小于主元则与i+1交换,最后会将主元放到中间位置.

def partition(A,p,r):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j] <= x:
            i += 1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
    tmp = A[r]
    A[r] = A[i+1]
    A[i+1] = tmp
    return i+1
A = [2,8,7,1,3,5,6,4]
p = partition(A,0,len(A)-1)
print(p) # 3
print(A) # [2, 1, 3, 4, 7, 5, 6, 8]

使用分治的思想,将小于主元的部分与大于主元的部分也递归的进行同样的操作,最终即可完成整个数组的排序:

def quicksort(A,p,r):
    if p<r:
        q = partition(A,p,r)
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)
A = [2,8,7,1,3,5,6,4]
quicksort(A,0,len(A)-1)
print(A)  # [1, 2, 3, 4, 5, 6, 7, 8]

快速排序的随机化版本

快速排序最理想的情况是选取的所有主元都是中位数,这时时间复杂度为\Theta ( n \lg n ),最坏的情况是每次主元都选取到最大值或最小值,导致大于和小于主元的两个类别严重不均衡,这时的复杂度为\Theta \left( n ^ { 2 } \right).对于平均的情况,"好"和"坏"的情况随机出现,快速排序复杂度是\Theta ( n \lg n ),与最好的情况的区别只是隐含的常数因子要略大一些.

在工程实际中,待排序的数据并不一定是随机的,那么我们就不能用平均情况的复杂度,解决这个问题也很简单,对快速排序加一个随机抽样就可以了:

import random

def randomized_partition(A,p,r):
    i = random.randint(p,r)
    tmp = A[r]
    A[r] = A[i]
    A[i] = tmp
    return partition(A,p,r)

def randomized_quicksort(A,p,r):
    if p<r:
        q = randomized_partition(A,p,r)
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)
A = [2,8,7,1,3,5,6,4]
randomized_quicksort(A,0,len(A)-1)
print(A)

快速排序 vs 堆排序 vs 并归排序

工程时间中使用最多的排序方法是快速排序,个人认为主要原因有以下两点:

  1. 虽然他们的时间复杂度都是\Theta ( n \lg n ),但是快速排序的常数因子是最小的.
  2. 堆排序每次从根节点拿数据,然后维护堆的性质,每次都需要读写很多数据,这需要大量的磁盘读写,而快速排序通过分治的方法,磁盘读写相对较小.
posted @ 2019-02-07 20:34:09
评论加载中...

发表评论