Python3 快速排序

r囧r小猫 2023-06-12 06:25 2阅读 0赞

参考：《算法图解》第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\]