分治策略-快速排序.md

基础思想

  • 用首元素xx作划分标准,将输入数组AA划分成不超过xx的元素构成的数组ALA_L,大于xx的元素构成的数组ARA_R。其中,AL,ARA_L,A_R从左到右存放数组AA的位置。

  • 递归地堆子问题ALA_LARA_R进行排序,直到子问题规模为11时停止。

伪代码

算法:Quicksort(A,p,r)

输入:数组A[p..r]

输出:排好序的数组A

1
2
3
4
5
if p < r
then q <- Partition(A, p, r)
A[p]<->A[q]
Quicksort(A, p, q-1)
Quicksort(A, q+1, r)

初始置p=1, r=n,然后调用上述算法。

1
2
3
4
5
6
7
8
9
10
11
x <- A[p]
i <- p
j <- r + 1
while true do
repeat j <- j - 1
until A[j] <= x // 不超过首元素的
repeat i <- i + 1
until A[i] > x // 比首元素大的
if i < j
then A[i] <-> A[j]
else return j

划分时间复杂度

  • 最坏情况:

    W(n)=W(n1)+n1W(1)=0W(n)=n(n1)/2 W(n)=W(n-1)+n-1 \\ W(1)=0 \\ W(n)=n(n-1)/2

  • 最好情况:

    T(n)=2T(n/2)+n1T(1)=0T(n)=Θ(nlogn) T(n) = 2T(n/2)+n-1 \\ T(1) = 0 \\ T(n) = \varTheta(n \log {n})

    利用生成递归树计算复杂度也是O(nlogn)O(n\log {n})

  • 平均时间复杂度

    首元素排好序后处在1,2,...,n1,2,...,n,各种情况概率为1/n1/n

    • 首元素出现在位置11T(0),T(n1)T(0), T(n-1)

    • 首元素出现在位置22T(1),T(n2)T(1), T(n-2)

    • 首元素出现在位置n1n-1: T(n),T(1)T(n), T(1)

    • 首元素出现在位置nnT(n1),T(0)T(n-1), T(0)

    子问题工作来量为2[T(1)+T(2)+...+T(n1)]2[T(1)+T(2)+...+T(n-1)]

    划分工作两为n1n-1

    T(n)=1nk=1n1(T(k)+T(nk))+n1T(n)=2nk=1n1T(k)+n1T(1)=0T(n)=Θ(nlogn) T(n) = \frac{1}{n}\sum_{k=1}^{n-1}(T(k)+T(n-k))+n-1 \\ T(n) = \frac{2}{n}\sum_{k=1}^{n-1}T(k)+n-1 \\ T(1) = 0 \\ T(n) = \varTheta(n \log {n})

    首元素划分后每个位置概率相等。

算法实现

小结

  • 分支策略

  • 子问题划分由首元素决定

  • 最坏情况时间:O(n2)O(n^2)

  • 平均情况时间:O(nlogn)O(n\log{n})

作者

Hu

发布于

2021-09-07

更新于

2021-08-25

许可协议

评论