快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。
那么分而治之(D&C)是一种怎样的策略呢?
分而治之
分而治之(D&C)的要点只有两个:
D&C不是一种解决问题的算法,而是一种解决问题的思路。比如看下面这个例子: 这是一个数字数组:
你需要将这些数字相加,并返回结果。使用循环可以很轻松地解决这个问题:
def sum(arr):
"""一个数组元素相加的循环"""
total = 0
for i in arr:
total += i
return total
print(sum([2, 4, 6]))
但是如何使用递归函数来完成这种任务呢?
这就是基线条件
下面用代码实现这个过程:
def sum(arr):
"""计算列表的各元素总和"""
if arr == []:
return 0
else:
return arr[0] + sum(arr[1:])
s = sum([2, 4, 6])
print(s)
说了这么多,却好像还是在说递归的知识,这和快速排序有什么关系呢?
快速排序
对于排序算法来说,最简单的数组是什么样的?对,没错,最简单的数组就是不需要排序的数组:
因此,在涉及多个元素的数组进行排序的时候,我们可以利用分而治之策略:将数组分解,直到满足基线条件为止。
简要叙述一下快速排序的基本思想:
可能有小伙伴到这里又懵了,这不还是没有说清楚快速排序到底是怎么排的嘛。
客官别急,下面来说快速排序的具体实现步骤:
用一个例子来说明:
下面用代码实现快速排序:
def quicksort(array):
"""快速排序"""
if len(array) < 2:
return array # 基线条件:为空或者只包含一个元素的数组是有序的
else:
pivot = array[0] # 递归条件
less = [i for i in array[1:] if i <= pivot] # 由所有小于或等于基准值的元素组成的子数组
greater = [i for i in array[1:] if i > pivot] # 由所有大于基准值的元素组成的子数组
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
再谈大O表示法
快速排序的独特之处在于,其速度取决于选择的基准值。这也就产生了最佳情况和最糟情况之分。
在最佳情况下,快速排序的运行时间为O(n ㏒n)。 在最糟情况下,快速排序的运行时间为O(n²)。
说明:最佳情况也是平均情况。
我们一般使用大O表示法都是指的算法的平均情况,所以我们一般认为快速排序的运行时间为O(n ㏒n)。至于何为最佳情况和最糟情况,这里不再过多阐述了。
小结
每天学习一点点,每天进步一点点。