排序算法-快速排序

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

原理

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

实现过程

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

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

基准值: 3

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

基准值: 3

小于基准值的元素: 2

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

基准值: 3

大于基准值的元素: 4

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

基准值: 3

小于基准值的元素: 1

列表: [2, 1(i上一轮位置), 1(此时j位置), 4, 5]
i像右侧开始比大小时 i 和 j 已经相等了,说明已经遍历完所有元素,这个时候把基准值赋值到 i 和 j 的共同位置即可完成此次的排序

基准值: 3

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

代码

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 #分区已经只有一个元素了

#空间复杂度高,但是理解非常简单
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分区