quicksort (A,p,r) if p < r // Partition the subarray around the pivot, which ends up in A[q]. q = partition (A,p,r) quick_sort (A,p,q - 1 ) quick_sort (A,q + 1 ,r) partition (A,p,r) x = A [r] i = p - 1 // highest index into the low side 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 T ( n ) = T ( n − 1 ) + T ( 0 ) + Θ ( n ) = T ( n − 1 ) + Θ ( n ) \begin{aligned} T(n) &= T(n-1) + T(0) + \Theta(n) \\ &= T(n-1) + \Theta(n) \\ \end{aligned} T ( n ) = T ( n − 1 ) + T ( 0 ) + Θ ( n ) = T ( n − 1 ) + Θ ( n )
可得
T ( n ) = Θ ( n 2 ) T(n) = \Theta(n^2) T ( n ) = Θ ( n 2 )
T ( n ) = 2 T ( n / 2 ) + Θ ( n ) T(n) = 2T(n/2) + \Theta(n) T ( n ) = 2 T ( n /2 ) + Θ ( n )
可得
T ( n ) = Θ ( n l g n ) T(n) = \Theta(nlgn) T ( n ) = Θ ( n l g n )
相关信息
假设每次划分都会分为 9 : 1, 则有
T ( n ) = T ( 9 n / 10 ) + T ( n / 10 ) + Θ ( n ) = Θ ( n l g n ) T(n) = T(9n/10) + T(n/10) + \Theta(n) = \Theta(nlgn) T ( n ) = T ( 9 n /10 ) + T ( n /10 ) + Θ ( n ) = Θ ( n l g n )
randomized_quicksort (A,p,r) if p < r q = randomized_partition (A,p,r) randomized_quicksort (A,p,q - 1 ) randomized_quicksort (A,q + 1 ,r) randomized_partition (A,p,r) i = random (p,r) exchange A [r] with A [i] return partition (A,p,r) T ( n ) = m a x { T ( q ) + T ( n − 1 − q ) : 0 ≤ q ≤ n − 1 } + Θ ( n ) T(n) = max\{ T(q) + T(n - 1 - q) : 0 \le q \le n - 1 \} + \Theta(n) T ( n ) = ma x { T ( q ) + T ( n − 1 − q ) : 0 ≤ q ≤ n − 1 } + Θ ( n )
使用替换法分析，假设 T(n) ≤ cn²，则有
T ( n ) ≤ m a x { c q 2 + c ( n − 1 − q ) 2 : 0 ≤ q ≤ n − 1 } + Θ ( n ) = c ⋅ m a x { q 2 + ( n − 1 − q ) 2 : 0 ≤ q ≤ n − 1 } + Θ ( n ) \begin{aligned} T(n) &\le max\{ cq^2 + c(n-1-q)^2 : 0 \le q \le n - 1 \} + \Theta(n) \\ &= c \cdot max\{ q^2 + (n-1-q)^2 : 0 \le q \le n - 1 \} + \Theta(n) \end{aligned} T ( n ) ≤ ma x { c q 2 + c ( n − 1 − q ) 2 : 0 ≤ q ≤ n − 1 } + Θ ( n ) = c ⋅ ma x { q 2 + ( n − 1 − q ) 2 : 0 ≤ q ≤ n − 1 } + Θ ( n )
又
q 2 + ( n − 1 − q ) 2 = q 2 + ( n − 1 ) 2 − 2 q ( n − 1 ) + q 2 = ( n − 1 ) 2 + 2 q ( q − ( n − 1 ) ) ≤ ( n − 1 ) 2 \begin{aligned} q^2 + (n-1-q)^2 &= q^2 + (n-1)^2 - 2q(n-1) + q^2 \\ &= (n-1)^2 + 2q(q-(n-1)) \\ &\le (n-1)^2 \end{aligned} q 2 + ( n − 1 − q ) 2 = q 2 + ( n − 1 ) 2 − 2 q ( n − 1 ) + q 2 = ( n − 1 ) 2 + 2 q ( q − ( n − 1 )) ≤ ( n − 1 ) 2
可得
T ( n ) ≤ c ( n − 1 ) 2 + Θ ( n ) ≤ c n 2 − c ( 2 n − 1 ) + Θ ( n ) ≤ c n 2 \begin{aligned} T(n) &\le c(n-1)^2 + \Theta(n) \\ &\le cn^2 - c(2n - 1) + \Theta(n) \\ &\le cn^2 \end{aligned} T ( n ) ≤ c ( n − 1 ) 2 + Θ ( n ) ≤ c n 2 − c ( 2 n − 1 ) + Θ ( n ) ≤ c n 2
因此
T ( n ) = Θ ( n 2 ) T(n) = \Theta(n^2) T ( n ) = Θ ( n 2 )
引理1
快速排序的运行时间是 O ( n + X ) \mathcal{O}(n+X) O ( n + X ) X X X
引理2
对于 n 个元素的数组 z 1 < z 2 < . . . < z n z_1 < z_2 < ... < z_n z 1 < z 2 < ... < z n z i z_i z i z j z_j z j Z i j Z_{ij} Z ij z i z_i z i z j z_j z j
引理3
对于 n 个元素的数组 z 1 < z 2 < . . . < z n z_1 < z_2 < ... < z_n z 1 < z 2 < ... < z n z i z_i z i z j z_j z j 2 / ( j − i + 1 ) 2/(j-i+1) 2/ ( j − i + 1 )
证明
P r { z i is compared with z j } = P r { z i or z j is the first pivot chosen from Z i j } = P r { z i is the first pivot chosen from Z i j } + P r { z j is the first pivot chosen from Z i j } = 2 j − i + 1 \begin{aligned} Pr\{z_i \text{ is compared with } z_j \} &= Pr\{z_i \text{ or } z_j \text{ is the first pivot chosen from } Z_{ij} \} \\ &= Pr\{z_i \text{ is the first pivot chosen from } Z_{ij}\} + Pr\{z_j \text{ is the first pivot chosen from } Z_{ij}\} \\ &= \frac{2}{j-i+1} \end{aligned} P r { z i is compared with z j } = P r { z i or z j is the first pivot chosen from Z ij } = P r { z i is the first pivot chosen from Z ij } + P r { z j is the first pivot chosen from Z ij } = j − i + 1 2
定理
对于 n 个不同的元素的数组，随机快速排序的期望运行时间是 O ( n l g n ) \mathcal{O}(nlgn) O ( n l g n )
证明
X = ∑ i = 1 n − 1 ∑ j = i + 1 n X i j X = \sum_{i=1}^{n-1}\sum_{j=i+1}^n X_{ij} X = i = 1 ∑ n − 1 j = i + 1 ∑ n X ij
其中 X i j = I { z i is compared with z j } X_{ij} = I\{z_i \text{ is compared with } z_j\} X ij = I { z i is compared with z j }
E [ X ] = E [ ∑ i = 1 n − 1 ∑ j = i + 1 n X i j ] = ∑ i = 1 n − 1 ∑ j = i + 1 n E [ X i j ] = ∑ i = 1 n − 1 ∑ j = i + 1 n P r { z i is compared with z j } = ∑ i = 1 n − 1 ∑ j = i + 1 n 2 j − i + 1 = ∑ i = 1 n − 1 ∑ k = 1 n − i 2 k + 1 < ∑ i = 1 n − 1 ∑ k = 1 n 2 k = ∑ i = 1 n − 1 O ( l g n ) = O ( n l g n ) \begin{aligned} E[X] &= E\left[ \sum_{i=1}^{n-1}\sum_{j=i+1}^n X_{ij} \right] \\ &= \sum_{i=1}^{n-1}\sum_{j=i+1}^n E[X_{ij}] \\ &= \sum_{i=1}^{n-1}\sum_{j=i+1}^n Pr\{ z_i \text{ is compared with } z_j \} \\ &= \sum_{i=1}^{n-1}\sum_{j=i+1}^n \frac{2}{j-i+1} \\ &= \sum_{i=1}^{n-1}\sum_{k=1}^{n-i} \frac{2}{k+1} \\ &< \sum_{i=1}^{n-1}\sum_{k=1}^{n} \frac{2}{k} \\ &= \sum_{i=1}^{n-1} \mathcal{O}(lgn) \\ &= \mathcal{O}(nlgn) \end{aligned} E [ X ] = E [ i = 1 ∑ n − 1 j = i + 1 ∑ n X ij ] = i = 1 ∑ n − 1 j = i + 1 ∑ n E [ X ij ] = i = 1 ∑ n − 1 j = i + 1 ∑ n P r { z i is compared with z j } = i = 1 ∑ n − 1 j = i + 1 ∑ n j − i + 1 2 = i = 1 ∑ n − 1 k = 1 ∑ n − i k + 1 2 < i = 1 ∑ n − 1 k = 1 ∑ n k 2 = i = 1 ∑ n − 1 O ( l g n ) = O ( n l g n )
