【有书共读】《算法与数据结构题目最优解》（在线编程题总结9）
该书第九章——《其它题目》，旨在练习实际的编程能力，这里我列举一个快速排序的简化版本，参考我的个人博客：https://blog.csdn.net/zichen_ziqi/article/details/83745156。
排序算法中的快排是面试过程中必备的一个基础，所以应该掌握，具体原理介绍见：戳我或百度百科，不详说，这里介绍一下常见的几种python代码：
1、见过最多的一种（Partition函数 + quickSort函数递归）
# 快速排序
def quick_sort(array, l, r):
if l < r:
q = partition(array, l, r)
quick_sort(array, l, q - 1)
quick_sort(array, q + 1, r)
def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[r] = array[r], array[i + 1]
return i + 1
if __name__=="__main__":
arr = [int(i) for i in input().split()] # 输入待排序列
quick_sort(arr,0,len(arr)-1) # 快速排序
print(" ".join(str(i) for i in arr)) # 输出排序结果
运行结果：
2、百度百科版（相当简洁，容易理解与记忆）
百度百科这个平台真的不错，相当专业，如果大家在阅读查资料的时候看到问题或bug，可以第一时间写邮件反馈，工作人员很快就会回复并完善。如：
#quick sort def quickSort(array): if len(array) < 2: # 基线条件（停止递归的条件） return array else: # 递归条件 baseValue = array[0] # 选择基准值 # 由所有小于基准值的元素组成的子数组 less = [m for m in array[1:] if m < baseValue] # 包括基准在内的同时和基准相等的元素，在上一个版本的百科当中，并没有考虑相等元素 equal = [w for w in array if w == baseValue] # 由所有大于基准值的元素组成的子数组 greater = [n for n in array[1:] if n > baseValue] return quickSort(less) + equal + quickSort(greater) # 示例： array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12] print(quickSort(array)) # 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]当时上一版本的代码为：
#quick sort def quickSort(array): if len(array) < 2: # 基线条件（停止递归的条件） return array else: # 递归条件 baseValue = array[0] # 选择基准值 # 由所有小于基准值的元素组成的子数组 less = [m for m in array[1:] if m < baseValue] # 由所有大于基准值的元素组成的子数组 greater = [n for n in array[1:] if n > baseValue] return quickSort(less) + [baseValue] + quickSort(greater) # 示例： array = [2,3,5,7,1,4,6,10,15,9,17,12] print(quickSort(array)) # 输出为[1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 15, 17]
确实当考虑相同数据的时候，存在问题（相同元素只有一个元素了），如下：
# 示例： array = [2,3,5,7,1,4,6,10,7,9,5,12] print(quickSort(array)) # 输出为[1, 2, 3, 4, 5, 6, 7, 9, 10, 12]
当时，和另外一个小伙伴发现这个问题后，尝试第一种改正方案（就添加了一个等号，当然也可以加在greater那一行），具体如下：
所以现在的快速排序代码为：
