排序算法-快速排序

图灵奖得主C. A. R. Hoare(托尼·霍尔)于1960时提出来的排序算法,使用非常广泛,速度也很快

原理

总结为:给每一步的基准值找到它正确索引位置的过程.
首先,选一个基准值(可以选第一个,可以选最后一个,可以选中间,本文选第一个),根据和基准值比大小分割成左边分区(比基准值小)和右边分区(比基准值大),利用分而治之递归处理左右两个分区(将每个分区再重复选基准值和分区),最终达到每个分区只有一个元素的时候即为基准条件(返回分区合并后的列表),归纳条件为分区的头和尾的游标不相等.这里需要仔细理解下分区递归处理.

实现过程

先实现原地快速排序的方法, 给定一个无序列表 [3, 4, 1, 2, 5], 还需要为了左右开始遍历列表行程分区的2个游标 i(左侧) 和 j(右侧):

  1. 选定初始值为数组第一个元素 (选拔该次排序列表的基准值条件)

    基准值: 3

    列表:[3, 4, 1, 2, 5]

  2. 从列表末端向左侧开始进行对比,如果比基准值大就继续找(目的是把无序列表按照基准值为分界线分成左右2个分区),比基准值小的说明该位置的元素应该分配到基准值的左侧,而此时基准值已经被取走了,相当于左侧第一个元素的位置是空的,于是把该值赋予到左侧第一个

    基准值: 3

    小于基准值的元素: 2

    列表:[2, 4, 1, 2(右侧游标j), 5]

  3. 因为找到了比基准值小的元素并且进行了重新赋值,所以现在2 的位置上相当于是空的(因为已经把2赋予给了列表第一个), 所以需要从左侧开始找比基准值大的元素.找到了 4 后进行和上一轮的游标j的值进行赋值操作

    基准值: 3

    大于基准值的元素: 4

    列表: [2, 4(i位置), 1, 4(j上一轮位置,进行赋值为4), 5]

  4. 左侧已经找到了比基准值大的,所以又轮到右侧继续从 4 的索引位置开始向左寻找,并且找到了 1 比基准值小.进行和上一轮的i索引的值进行赋值操作

    基准值: 3

    小于基准值的元素: 1

    列表: [2, 1(i上一轮位置), 1(此时j位置), 4, 5]

  5. i像右侧开始比大小时 i 和 j 已经相等了,说明已经遍历完所有元素,这个时候把基准值赋值到 i 和 j 的共同位置即可完成此次的排序

    基准值: 3

    列表: [2, 1, 3, 4, 5]
    这一轮已经进行完 分区的操作 以基准值 3 分为了 [2,1][4, 5]
    接下来的操作就是把这2个继续 按照 步骤操作,直到每个分区只有一个元素的时候就完成了所有列表的排序

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quickSort(list:'list', start, end)->list:
k = start #记录初始位置的游标
j = end #记录结束位置的游标
if start < end: # 基准条件 最外层的list分区里有2个索引, 因为至少2个元素才能进行排序
init = list[k] #初始化一个start位置的元素当基准值,最后需要填充到 j = k 索引的位置上
while j != k: #左右两侧不相等就说明2个游标未遍历完所有元素
while j > k and list[j] >= init: #遍历右侧的条件
j -= 1
list[k] = list[j] #进行赋值操作
while k < j and list[k] <= init: #遍历左侧的条件
k += 1
list[j] = list[k] #进行赋值操作
list[j] = init #该分区已经全部赋值完,把基准位置的值填入 j = k 的索引
quickSort(list, start, k-1) #把该列表里的左右分区递归的进行处理
quickSort(list, k+1, end) #把该列表里的左右分区递归的进行处理
return list #分区已经只有一个元素了
1
2
3
4
5
6
7
8
#空间复杂度高,但是理解非常简单
def quickSort(list:'list')->list:
if len(list)<2: #基准条件
return list
init = list[0] #选基准值
left = [val for val in list[1:] if val <= init] #比大小选出来左侧分区
right = [val for val in list[1:] if val > init] #比大小选出来左侧分区
return quickSort(left) + [init] + quickSort(right) #递归处理 left 和 right分区
Bowen wechat
博客文章会同步更新在公众号[后端浪里个浪]
一毛也是爱~