快速排序的时间复杂度为 O(nlogn),空间复杂度为 O(n).根据 @张小牛 的文章 快速排序 (Quick Sort) 详解 ,证明最优的排序算法,其时间复杂度可为 O(nlogn),对应的空间复杂度可为 O(n).快速排序可实现理论最优效率,这可能是快速排序比较重要的原因吧.
我们基于 Python 学习写一下快速排序吧.
先给定一个长度为 10 的列表 data = [5, 4, 7, 8, 2, 7, 8, 5, 6, 3],如下:
初始列表
有了一个列表,看起来会直观多了吧,但是我们想放着不管.快速排序的主旨很简单:找一个标杆数,称为 X,然后根据 X 把数组的数分堆,小于 X 的全放左边,大于 X 的全放右边,就可以啦.对于实际情况呢,我们还需要考虑等于 X 的情况,我将其与小于归为一起,即数组排列后,形成 "小于等于 X" + "大于 X" 两部分.
就是说,快速排序的主要步骤就是:找 X + 跟 X 比大小排列?
你可能会疑惑,只是按 "比 X 大或比 X 小" 排列数组,怎么能得到完整的排序呢.一次排列几乎不可能排好,但我们可以将排了一次的数组上,切分为 "小于等于 X" 和 "大于 X" 两块,再对这两块分别再找标杆数 X'和 X'',接着再分别排序.最后组合再一起,就得到了排列了两次的数组,其顺序肯定更接近完美序列.那么我们继续这么 "切分→找标杆数→排列" 操作下去呢?在此例中,由于每一分堆总小于右侧的分堆,而大于左侧的分堆,同时每个分堆内部已排好序,因此整个序列排序完成.
以上这种操作叫做 "迭代",可以对数组不断地切分并采用同样的排列模式进行排列,直到迭代条件不再满足,则停止迭代.在这里,我们选择切分后数组的长度大小,作为迭代的条件,细节在后面详述.
我们不妨先试着试验一下,找 X,然后将数组跟 X 比大小排列.我没有研究哪一个当标杆好,不如就选第一个数字吧.
选择第一个数字为 "标杆数"
下面我们就要依据 "标杆数",也就是数字 "5"(其序数为 0),对其余部分进行分堆了.我们想分为 "<=5" 与 ">5" 的两部分,并使前者位于左侧,后者位于右侧,操作步骤如下:
1. 命名左侧序数为 i,初始 i = 1;命名右侧序数为 j,初始 j = len(data)-1(即最后一位).
初始化 i,j
2. 让 j 开始移动并进行判断:
若 j 所在的数字 <=5,则让 i 开始向右移动,直到 i 所在的数字 > 5,接着交换 data 中 i, j 所对应的数字,即:
data[i], data[j] = data[j], data[i]
若 j 所在数字 >5,则忽略,继续向左移动.
3. 当 j == i 时,意味着交换结束,列表除了首位的 "标杆数",其余部分分为 <=5 和> 5 两堆,那么我们还应该把 "5" 放到这两堆中间,让列表看上去更有序.即:
data[0], data[j] = date[j], data[0]
注意:如果 j 此时不在列表中间呢,比如由于数据特殊,j 最终停在在首,尾处呢?
不能交换
可以交换
考虑到这一点,我们就可以意识到,要做的是把一开始找的标杆放到应有的位置上,即最后一个 <=5 的数的位置.因此,我们在交换前加一个判断:
4. 结束操作,返回此时的 data.
if data[j] <= data[0]:
data[0], data[j] = data[j], data[0]
容易看到,由于我让 j 的移动占主动性,j 先找到一个 <=5 的数后,i 才能开始行动找> 2 的数.那么当 j,i 会,请问 j 最终会停在 <=5 还是> 5 的数字上呢?
答案是:对于这里给出的 data,j 总是会停在 <=5 的数字上,或者说对于 len(data)>5 的 data,j 与 i 总是相遇在最右的 "<= 标杆数" 的位置上(仔细想一想~).
这样做是为了便于 data[j] 与 data[0] 交换,所以让 j 先行;如果让 i 先行,那么相反的,i,j 通常相遇在最左的 "> 标杆数" 的位置上,这样不利于 data[i] 与 data[0] 交换.
对于 len(data) == 1 or len(data) == 2 的两种例外情况,留给读者思考.伪代码如下:
以上部分讲的是单次排序的(啰嗦)细节,整个快速排序是若干次单次排序的迭代,下面讲解一下迭代部分:
if len(data) == 2:
if data[j] <= data[0]:
data[0], data[j] = data[j], data[0]
return quicksort(data[left_part]) + quicksort(data[right_part])
if len(data) == 1:
return data
首先简化模型,我们把不直观的 "数字比大小" 转换为直观的 "图形排序",将 data 中的 "标杆数 5" 及 <=5 的数替换为"▲",将> 5 的数替换为 "█",则有:
接着,用上述的 i,j 排序规则操作一遍之后,得到:
是不是清晰许多?
进行迭代,我们要做的就是把分大小排序的 data 拆分为两个 data,分界线即为 "标杆数",然后分别对两个拆分 data 排序,直至抵达迭代终止条件(len(data) <= 1 即终止).
对示例列表进行快速排序的原理如下:
完整代码如下:
完结撒花~
def quicksort(data): #快速排序
stone = data[0]
i = 1
j = len(data)-1
if len(data) > 1: #分为len(data) >2和len(data) == 2两种情况,可合并
while j > i:
if data[j] <= stone:
if data[i] > stone:
data[j], data[i] = data[i], data[j]
else:
i += 1
else:
j -= 1
if data[j] <= stone: #当len(data) == 2时只执行此部分
data[0], data[j] = data[j], data[0]
return quicksort(data[:j]) + quicksort(data[j:])
else: #迭代终止条件,len(data) <= 1
return data
以上 .
来源: http://www.jianshu.com/p/7631d95fdb0b