使用Python实现快速排序算法

首先，我们来看一下快速排序算法的思想：


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


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


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


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


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


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


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


举个例子：

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

复制代码

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


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