【练习】快速排序

项目简介

快速排序

知识模块

• Python 编程语言

知识点

• 递归
• 分区操作
• 列表操作
• 算法复杂度分析

受众

• 初级测试开发工程师
• 初级Python开发工程师

作业要求

编写一个Python程序，实现快速排序。

解题思路

1. 首先选择一个基准元素，通常是选择待排序列表的第一个元素。

2. 将列表分成两部分，小于基准元素的元素放在左边，大于基准元素的元素放在右边。这个过程称为分区（partition）。

3. 递归地对左右两个分区进行快速排序。也就是将左边的分区作为新的子列表，再次选择基准元素，并进行分区操作。对右边的分区也是同样的操作。

4. 递归的结束条件是分区中只有一个元素或为空，此时分区已经是有序的。

5. 最后将所有的分区合并起来，即可得到排好序的列表。

完整代码

def quickSort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]  # 选取数组中间元素作为基准值
    left = [x for x in arr if x < pivot]  # 小于基准值的部分放在左边列表
    middle = [x for x in arr if x == pivot]  # 等于基准值的部分放在中间列表
    right = [x for x in arr if x > pivot]  # 大于基准值的部分放在右边列表

    return quickSort(left) + middle + quickSort(right)  # 合并结果返回

代码讲解

1. def quickSort(arr): 定义了一个名为quickSort的函数，它接受一个参数arr，即待排序的列表。

2. if len(arr) <= 1: 检查列表的长度是否小于等于1，如果是，则直接返回列表本身，因为长度小于等于1的列表已经是有序的。

3. pivot = arr[len(arr) // 2] 选择列表的中间元素作为基准值。使用//是为了得到整数结果，确保索引取到中间元素。

4. left = [x for x in arr if x < pivot] 使用列表推导式创建了一个新列表left，其中包含所有小于基准值的元素。

5. middle = [x for x in arr if x == pivot] 使用列表推导式创建了一个新列表middle，其中包含所有等于基准值的元素。

6. right = [x for x in arr if x > pivot] 使用列表推导式创建了一个新列表right，其中包含所有大于基准值的元素。

7. return quickSort(left) + middle + quickSort(right) 通过递归调用quickSort函数分别对left列表和right列表进行排序，并将排序好的left列表、middle列表和right列表拼接成完整的有序列表，然后返回该列表作为函数的结果。