vlambda博客
学习文章列表

排序算法系列——快速排序

什么是快速排序?

快速排序,顾名思义它排序的速度十分的快。

它快到什么程度呢?

C语言标准库中的qsort函数就是使用快速排序实现的!

说到快速排序,离不开两个重要的概念:递归 和 分治算法(Divide ans conquer, D&C)。

如果要讲清楚这两个概念,可以单独写两篇文章出来了。

因此这里不做深入,只简单介绍一下:

递归:重复调用自己的函数。一般由两个部分组成基线条件 和 递归条件,程序在符合基线条件的时候返回,在符合递归条件的时候调用自己。

分治算法(Divide ans conquer, D&C): 将大的问题化解为相同类型的小问题。一种著名的递归式问题解决办法,一般分为两个步骤,首先找出尽可能简单的基线条件,然后将递归的将问题分解为小问题,直到小问题符合基线条件。

假如还不太明白这两个概念,没关系,看下面的例子就可以了。

排序过程

既然快速排序的核心思想是D&C,那么它的基线条件递归条件分别是什么呢?

首先我们思考一下,什么样的数组需要排序?

长度为0的数组需要排序吗?不需要。因为它的没有顺序的概念。

长度为1的数组需要排序吗?不需要。因为可以把它看做一个有序数组了。

长度为2的数组需要排序吗?需要。因为并不能确定它的顺序。

因此,我们可以把长度为0或1的数组设为是基线条件
递归条件则是长度大于1的数组

举个例子:

假如现在有一个无序数组disorder_arr = [4,2,19,10,-1]

第一步:
我们取第一个数4基准数,

然后将小于4的分成一类:[2,-1],放在4的左边

大于4的分成一类:[19,10],放在4的右边。

第二步:
长度大于1 的数组重复上面的步骤,如下图所示:

直到所有的数组都符合基线条件(长度为0或1)后, 我们便可得到一个排列有序的数组了。

写一段代码

代码依然是使用Python3实现的

# quickSort.py
class Solution:
def quick(self, disorder_arr: list):
# 递归实现
if len(disorder_arr) < 2: # 基线条件
return disorder_arr

base_num = disorder_arr[0] # 基数,取数组第一个数
min_arr = [] # 小于基数的数
max_arr = [] # 大于基数的数
for i in range(1, len(disorder_arr)): # 遍历一遍数组,
if disorder_arr[i] <= base_num:
min_arr.append(disorder_arr[i])
elif disorder_arr[i] > base_num:
max_arr.append(disorder_arr[i])

return self.quick(min_arr) + [base_num] + self.quick(max_arr) # 递归

总结

快速排序的原理是首先找到一个基准数,然后通过遍历数组, 将小于基准数的数分成一类,放在基准数的左边,大于基准数的数分成另一类,放在基准数的右边。

在最优情况下,快速排序算法的平均时间复杂度是O(nlogn), 但是最坏的情况下,它的时间复杂度也会达到O(n^2)

以上代码已上传至github[1]

欢迎大家友好交流[握手]


参考资料

[1]

github: https://github.com/alisen39/algorithm/blob/master/algorithms/sorting/quickSort.py