Python3 快速排序

mac2024-10-22  9

参考:《算法图解》第4章 快速排序 

$ 分而治之(divide and conquer,D&C) D&C算法是递归的,步骤: (1)找出基线条件,尽可能简单 (2)不断将问题分解,直到符合基线条件

提示:编写涉及数组的递归函数时,基线条件通常是数组为空或只包含一个元素。

$ 快速排序 (1)基线条件:数组为空或只包含一个元素 -> 不用排序,直接返回原数组即可 def quicksort(array):     if len(array) < 2:         return array          (2)从数组中选择一个元素作为 基准值(pivot) 暂时将元素的第一个元素作为基准值 -> 找出比基准值小的元素 和 比基准值大的元素 【例】 [33,15,10] 以33为基准值 [15,10] , 33 , []  -> 得到 一个由所有小于基准值的数字构成的子数组,基准值,一个由所有大于基准值的数字构成的子数组 这被称为 分区(partitioning),得到的两个子数组是无序的

如果这两个数组是有序的事情就好办了,于是要分别对子数组进行排序

quicksort([15,10]) + [33] + quicksort([]),不断对子数组进行快速排序,直到数组拆解为最简单的情况(最多只有一个元素)

$ 归纳证明 两步:基线条件 + 归纳条件 【例】证明自己能爬到梯子顶端 归纳条件:如果站在梯子的一个横档上,就能将脚放到上一个横档上 基线条件:脚已经放在第一个横档上

$ 快速排序代码

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,21,7]))

[10,5,2,3,21,7] 以10作为基准值 [5,2,3,7] ,[10], [21] [2,3],[5],[7] , [10] , [21] [],[2],[3] ,[5], [7], [10] , [21] -> [2,3,5,7,10,21]

 

最新回复(0)