八十一、最快最优的快速排序和优化
「@Author:Runsen」
❝编程的本质来源于算法,而算法的本质来源于数学,编程只不过将数学题进行代码化。「---- Runsen」
❞
快速排序
不久前,我在牛客中看到这样一个笑话,面试官让他写一个快速排序,结果他写了一个冒泡排序,虽说不是计算机专业的,还一直说没有写错,都不知道面试官为什么这么PASS。其实,一共有十大排序算法,最快最稳定的就是快速排序,简称快排。
quicksort 可以说是应用最广泛的排序算法之一,它的基本思想是分治法。基础的快速排序算法思想很简单,核心就是一句话:找到基准值的位置。
具体的过程其实和把大象装进冰箱这个问题一样,都可以分成三步:
「第一步,选择一个值作为基准值。」
「第二步,找到基准值的位置,并将小于基准值的元素放在基准值的前面,大于基准值的元素放在基准值的后面。」
「第三步,对基准值的左右两侧递归地进行这个过程。」
以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ]
为例,选择一个支点, index= (L+R)/2 = (0+7)/2=3
, 支点的值 pivot = arr[index] = arr[3] = 6
,接下来需要把 arr
中小于 6
的移到左边,大于 6
的移到右边,最后然后对基准值的左右两侧递归地进行这个过程。
快速排序最好用递归的代码实现,代码简单可读性前。
def quick_sort(b):
"""快速排序"""
if len(b) < 2:
return arr
# 选取基准,随便选哪个都可以,选中间的便于理解
mid = arr[len(b) // 2]
# 定义基准值左右两个数列
left, right = [], []
# 从原始数组中移除基准值
b.remove(mid)
for item in b:
# 大于基准值放右边
if item >= mid:
right.append(item)
else:
# 小于基准值放左边
left.append(item)
return quick_sort(left) + [mid] + quick_sort(right)
def quicksort(array):
if len(array) < 2:
# 基本情况下,具有0或1个元素的数组是已经“排序”的
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]))
快排优化
快排优化的方法就是:「合理选择pivot。」。我们知道,如果基准值选取不合理的话,快速排序的时间复杂度有可能达到 这个量级,也就是退化成和选择排序、插入排序等算法一样的时间复杂度。只有当基准值每次都能将排序区间中的数据平分时,时间复杂度才是最好情况下的 O(nlogn)
。
关于基准值选取的一个优化策略,「三点取中法。」
谓三点取中法,就是每一轮取排序区间的头、尾和中间
元素这三个值,然后把它们排序以后的中间值作为本轮的基准值。调整要选取的这三个值的位置。
我们就以上图为例,假设本轮的三个值分别为 2、9、7,中间值是 7,所以,本轮的基准值就是 7。
快排优化:「更快地分区」。快速排序的做法是从左向右依次与 pivot 比较,做交换,这样做其实效率并不高。
举个简单的例子,一个数组 [2, 1, 3, 1, 3, 1, 3]
,选第一个元素作为 pivot 是2,每次发现比2小的数会引起一次交换,一共三次。
然而,直观来说,其实只要将第一个3和最后一个1交换就可以达到这三次交换的效果。所以更理想的分区方式是从「两边向中间遍历」的双向分区方式,而不是从左到右,当然前提是基准值选择数组的中位数。
具体快速排序优化的代码如下所示。
'''
@Author:Runsen
@WeChat:RunsenLiu
@微信公众号:Python之王
@CSDN:https://blog.csdn.net/weixin_44510615
@Github:https://github.com/MaoliRUNsen
@Date:2020/12/21
'''
def quick_sort(nums, start, end):
if start >= end:
return
pivot = nums[start] # 基准值
low = start # 左指针
high = end # 右指针
while low < high:
while low < high and nums[high] >= pivot:
high -= 1
nums[low] = nums[high]
while low < high and nums[low] < pivot:
low += 1
nums[high] = nums[low]
nums[low] = pivot
quick_sort(nums, start, low - 1)
quick_sort(nums, low + 1, end)
if __name__ == '__main__':
nums = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(nums, 0, len(nums) - 1)
print(nums)
快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了,而且Python内置的sorted
就是快速排序。
虽然 Worst Case 的时间复杂度达到了O(n²)
,比如说顺序数列的快排。但是就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn)
的排序算法表现要更好,,比复杂度稳定等于 O(nlogn)
的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。
❝本文已收录 GitHub,传送门~[1] ,里面更有大厂面试完整考点,欢迎 Star。
❞
Reference
传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100
更多的文章
点击下面小程序
- END -