快速排序

本文最后更新于：2025年10月14日 晚上

递归

两个重要的条件：基线条件（停止条件） 递归条件（执行条件）

栈

与数组和了链表一样，是一种数据类型。类似于贴便签，顺序为后入先出。

递归中的调用栈

定义阶乘函数fac来理解其

1
2
3
4
5
def fac(x):
    if x==1:   #基线条件
        return 1
    else:   #递归条件
        return x * fact(x-1)

12

调用栈相当于帮助程序在调用子函数时记住母函数执行位置，以便返回后继续执行。

D&C(分而治之)

一种解决问题的思路

3

解决步骤：

  1. 找出极限条件
  2. 分解问题，直到符合基线条件

快速排序

一种算法

步骤：

  1. 选择基准值
  2. 将数组分为大于基准值的子数组和大于基准值的子数组
  3. 再对子数组进行快速排序

当数组为空或仅有一个数组时就无需排序，所以这是基准条件

图示

[33,10,15,7] 排序这个数组

取==33==为基准数

[10,15,7][33][ ]得到两个子数组，一个为空达到基准条件

取==10==为基准数

[7][10][15]+[33]+[ ]达到基准条件，快速排序完成

代码

1
2
3
4
5
6
7
8
def sort(array):
    if len(array) < 2:
        renturn array  #基线条件
    else:
        standard = array[0]  #默认选择第一个为基准值
        less = [for i in array[1:] if i <= standard]
        big = [for i in array[1:] if i > standard]
        return sort(less) + [standard] + sort(big)