通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分成两个子序列(sub-lists)。
算法步骤:
递归算法的时间复杂度公式: T [ n ] = a T [ n / b ] + f ( n ) T[n]=aT[n/b] + f(n) T[n]=aT[n/b]+f(n)
快速排序的最优情况是每一次取到的元素都刚好平分整个数组。此时时间复杂度的公式则为: T [ n ] = 2 T [ n / 2 ] + f ( n ) T[n]=2T[n/2]+f(n) T[n]=2T[n/2]+f(n), T [ n / 2 ] T[n/2] T[n/2]为平分后的子数组的时间复杂度, f ( n ) f(n) f(n)为平分这个数组所花的时间。
下面来推算一下,在最优的情况下快速排序时间复杂度的计算:
第一次递归: T [ n ] = 2 T [ n / 2 ] + n T[n] = 2T[n/2] + n T[n]=2T[n/2]+n;
令: n = n / 2 n = n/2 n=n/2,则有: T [ n ] = 2 { 2 T [ n / 4 ] + ( n / 2 ) } + n = 2 2 T [ n / ( 2 2 ) ] + 2 n T[n]=2\{2 \ T[n/4] + (n/2)\} + n = 2^2 T[n / (2^2)] + 2n T[n]=2{2 T[n/4]+(n/2)}+n=22T[n/(22)]+2n
令: n = n / ( 2 2 ) n = n / (2^2) n=n/(22),则有: T [ n ] = 2 3 T [ n / ( 2 3 ) ] + 3 n T[n] = 2^3 T[n/(2^3)]+3n T[n]=23T[n/(23)]+3n
若m次递归结束,则令: n = n / ( 2 m − 1 ) n=n/(2^{m-1}) n=n/(2m−1),有: T [ n ] = 2 m T [ 1 ] + m n T[n]=2^{m} T[1] + mn T[n]=2mT[1]+mn
于是得到: T [ n / ( 2 m ) ] = T [ 1 ] T[n/(2^m)]=T[1] T[n/(2m)]=T[1],则有: n = 2 m n=2^m n=2m,即: m = log 2 ( n ) m=\log_2(n) m=log2(n)。
故有: T [ n ] = 2 log 2 ( n ) T [ 1 ] + n log 2 ( n ) T[n] = 2^{\log_2(n)} T[1] + n \log_2(n) T[n]=2log2(n)T[1]+nlog2(n),其中 n n n为元素个数,当 n ≥ 2 n \geq 2 n≥2时, n log 2 ( n ) ≥ n n \log_2(n) \geq n nlog2(n)≥n,所以取后面的 n log 2 ( n ) n\log_2(n) nlog2(n);
综上所述:快速排序最优情况下时间复杂度为: Ω ( n log 2 ( n ) ) \Omega(n \log_2(n)) Ω(nlog2(n))。
在平均的情况下,设枢轴的关键字应该在第 k k k的位置( 1 ≤ k ≤ n 1 \leq k \leq n 1≤k≤n),那么:
T [ n ] = 1 n ∑ k = 1 n ( T [ k − 1 ] + T [ n − k ] ) + n = 2 n ∑ k = 1 n T [ k ] + n T[n]=\frac{1}{n} \sum_{k=1}^{n}(T[k-1] + T[n-k]) + n = \frac{2}{n} \sum_{k=1}^{n} T[k] +n T[n]=n1k=1∑n(T[k−1]+T[n−k])+n=n2k=1∑nT[k]+n
由数学归纳法可知,其数量级为 Θ ( n log 2 ( n ) ) \Theta(n \log_2(n)) Θ(nlog2(n))。
当我们选取的枢纽每次都是最大元素时,就是最差情况,待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个记录的子序列,注意另一个为空。如果递归树画出来,它就是一棵斜树。此时需要执行 n ‐ 1 n‐1 n‐1次递归调用,且第 i i i 次划分需要经过 n ‐ i n‐i n‐i 次关键字的比较才能找到第 i i i 个记录,是枢轴的位置,因此比较次数为:
∑ i = 1 n − 1 = ( n − 1 ) + ( n − 2 ) + + . . . + 1 = n ( n − 1 ) 2 \sum_{i=1}^{n-1} = (n-1) + (n-2) + + ... + 1 = \frac{n(n-1)}{2} i=1∑n−1=(n−1)+(n−2)++...+1=2n(n−1)
于是时间复杂度为: O ( n 2 ) O(n^2) O(n2)。
递归造成的栈空间的使用,最好情况,递归树的深度为 log 2 n \log_2n log2n,其空间复杂度也就为 Ω ( log ( n ) ) \Omega(\log(n)) Ω(log(n));最坏情况,需要进行 n ‐ 1 n‐1 n‐1递归调用,其空间复杂度为 O ( n ) O(n) O(n);平均情况,空间复杂度也为 Θ ( log ( n ) ) \Theta(\log(n)) Θ(log(n))。
由于关键字的比较和交换是跳跃进行的,因此,快速排序是一种不稳定的排序方法。
quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if (item > array[0] if reverse else item <= array[0])]) + [array[0]] + quick_sort([item for item in array[1:] if (item <= array[0] if reverse else item > array[0])])
def quick_sort(array: list, l: int, r: int, reverse: bool=False) -> None:
'''
array: 支持数值型数据,如整型与浮点型混合;支持全为字符串类型的数据;不支持字符串型与数值型混合。
l: 数据左侧游标(整型), r: 数据右侧游标(整型)
reverse: 是否降序, 默认采用升序。
'''
if l >= r:
return None
assert l >= 0
assert r >= 0
if l < r:
mid = partition(array, l, r, reverse=reverse)
quick_sort(array, l, mid - 1)
quick_sort(array, mid + 1, r)
def partition(array: list, l: int, r: int, reverse: bool=False) -> int:
'''
array: 数据(列表), l: 数据左侧游标(整型), r: 数据右侧游标(整型)
'''
value = array[r]
index = l - 1
for ind in range(l, r):
if (array[ind] > value if reverse else array[ind] <= value):
index += 1
array[index], array[ind] = array[ind], array[index]
array[index + 1], array[r] = array[r], array[index + 1]
return index + 1
def quick_sort(array: list, l: int, r: int, reverse: bool=False) -> None:
'''
array: 支持数值型数据,如整型与浮点型混合;支持全为字符串类型的数据;不支持字符串型与数值型混合。
l: 数据左侧游标(整型), r: 数据右侧游标(整型)
reverse: 是否降序, 默认采用升序。
'''
if l >= r:
return None
assert l >= 0
assert r >= 0
stack = []
stack.append(l)
stack.append(r)
while stack:
low = stack.pop(0)
high = stack.pop(0)
if high - low <= 0:
continue
value = array[high]
index = low - 1
for ind in range(low, high):
if (array[ind] > value if reverse else array[ind] <= value):
index += 1
array[index], array[ind] = array[ind], array[index]
array[index + 1], array[high] = array[high], array[index + 1]
stack.extend([low, index, index+2, high])