快捷搜索: 脱发

用python实现快速排序法

快速排序(Quick Sort)是一种常见的基于比较的排序算法,它的英文名称就是Quick Sort。它的基本思想是选择一个基准值,将列表中的元素分成小于基准值和大于基准值的两个子列表,然后递归地对两个子列表进行排序,最终将两个子列表和基准值组合起来形成一个有序的列表。快速排序算法的时间复杂度为O(n log n),是一种高效的排序算法。实现代码如下:

def quick_sort(arr):
    # 如果列表为空或只有一个元素,则直接返回
    if len(arr) < 2:
        return arr

    # 将第一个元素作为基准值
    pivot = arr[0]

    # 将列表中所有小于基准值的元素放在左边,大于基准值的元素放在右边
    left = [i for i in arr[1:] if i < pivot]
    right = [i for i in arr[1:] if i >= pivot]

    # 对左右子列表分别递归进行快速排序
    left_sorted = quick_sort(left)
    right_sorted = quick_sort(right)

    # 将左右子列表和基准值组合成排序后的列表
    return left_sorted + [pivot] + right_sorted

在这个示例代码中,我们首先定义了quick_sort()函数,它需要一个整数列表作为输入,返回一个排序后的整数列表。在函数内部,我们首先判断列表的长度是否小于2,如果是,则直接返回。否则,我们将第一个元素作为基准值,并将列表中所有小于基准值的元素放在左边,大于等于基准值的元素放在右边。然后,我们对左右子列表分别递归进行快速排序,并将左右子列表和基准值组合成排序后的列表。最后,我们返回排序后的列表。

然后,我们可以使用以下代码来测试quick_sort()函数:

arr = [5, 3, 8, 4, 2, 7, 1, 10, 6, 9]
sorted_arr = quick_sort(arr)
print(sorted_arr)

如果你运行上述代码,应该会得到以下输出结果:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

这说明quick_sort()函数能够正确地对整数列表进行快速排序。

经验分享 程序员 微信小程序 职场和发展