【有书共读】《算法与数据结构题目最优解》（在线编程题总结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那一行），具体如下：

【有书共读】《算法与数据结构题目最优解》（在线编程题总结9）

全站热榜

创作者周榜