永洪社区

标题: 使用Python实现快速排序算法 [打印本页]

作者: puffs 时间: 2024-9-19 11:16
标题: 使用Python实现快速排序算法
首先，我们来看一下快速排序算法的思想：

快速排序是一种高效的排序算法，其基本思想基于分治法（Divide and Conquer）策略，具体步骤如下：

选择基准值（Pivot）：从数组中选择一个元素作为基准值，通常选择第一个元素、最后一个元素、中间元素或随机元素。

分区操作（Partitioning）：重新排列数组，所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准后面。在这个分区退出之后，该基准就处于数组的中间位置。这个称为分区（partition）操作。

递归排序：递归地（Recursively）将小于基准值的子数组和大于基准值的子数组排序。

合并：由于在原地（in-place）排序，所以不需要合并步骤，排序过程在递归调用中完成。

快速排序的关键点在于它的递归性质和分区策略。以下是快速排序算法的一般步骤：
· 选择一个元素作为“基准”（pivot）。
· 将所有小于基准的元素移到基准的左边，将所有大于基准的元素移到它的右边，此时基准元素处于最终排序后的位置。
· 对基准左边和右边的子数组递归执行快速排序。

快速排序的性能通常比其他O(n log n)算法要好，因为它的内部循环（inner loop）可以在大多数的架构上很有效率地被实现出来。快速排序的平均时间复杂度为O(n log n)，但在最坏的情况下会退化到O(n^2)，尤其是当输入数组已经接近有序时。为了避免这种情况，通常会使用一些策略来选择基准值，比如随机选择或“三数取中”法。

举个例子：

<font size="3">def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
# 测试快速排序函数
arr = [10, 7, 8, 9, 1, 5]
print("原始数组：")
print("\t", arr)
sorted_arr = quick_sort(arr)
print("快速排序后的数组：")
print("\t", sorted_arr)</font>

复制代码

这段代码定义了一个 quick_sort 函数，它首先检查数组的长度，如果数组只有一个或没有元素，那么它已经是有序的，直接返回。否则，它会选择数组的第一个元素作为基准值（pivot），然后将数组分为两个子数组：一个包含小于或等于基准值的元素，另一个包含大于基准值的元素。这个过程称为分区（partitioning）。然后，函数递归地对这两个子数组进行快速排序，并最终将排序后的子数组和基准值合并。

文章来源：公众号Python学习与大数据分析

欢迎光临永洪社区 (https://club.yonghongtech.com/)