快速排序算法的基本思想以及Python实现

快速排序（Quick Sort）是一种高效的排序算法，采用分而治之（Divide and Conquer）的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

Java资深爱好者

415人浏览 · 2024-07-18 11:05:42

Java资深爱好者 · 2024-07-18 11:05:42 发布

基本思想

选择基准（Pivot）：从数列中挑出一个元素，称为“基准”（pivot）。
分区（Partitioning）：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归（Recursion）：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

Python 实现

下面是快速排序的Python实现：

python复制代码

	`def quicksort(arr):`
	`if len(arr) <= 1:`
	`return arr`
	`else:`
	`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) # 递归排序左右子序列，并合并结果`

	`# 示例`
	`arr = [10, 7, 8, 9, 1, 5]`
	`sorted_arr = quicksort(arr)`
	`print("Sorted array is:", sorted_arr)`

注意：在实际应用中，上述实现可能不是最优的，因为它在每次递归时都进行了列表的切片和合并操作，这会增加额外的时间复杂度。一种更优化的方式是使用原地分区（in-place partitioning），这样可以避免使用额外的空间来存储分区后的子列表。

原地分区快速排序的Python实现

python复制代码

	`def quicksort_inplace(arr, low, high):`
	`if low < high:`
	`# partition the array and get the partition index`
	`pi = partition(arr, low, high)`

	`# Separately sort elements before`
	`# partition and after partition`
	`quicksort_inplace(arr, low, pi-1)`
	`quicksort_inplace(arr, pi+1, high)`

	`def partition(arr, low, high):`
	`# 选择最后一个元素作为基准`
	`pivot = arr[high]`
	`i = low - 1 # 小于基准的元素的索引`
	`for j in range(low, high):`
	`# 如果当前元素小于或等于pivot`
	`if arr[j] <= pivot:`
	`i += 1`
	`arr[i], arr[j] = arr[j], arr[i]`
	`arr[i+1], arr[high] = arr[high], arr[i+1]`
	`return (i+1)`

	`# 示例`
	`arr = [10, 7, 8, 9, 1, 5]`
	`n = len(arr)`
	`quicksort_inplace(arr, 0, n-1)`
	`print("Sorted array is:", arr)`

这个版本的快速排序使用了原地分区技术，更加高效。

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

小参数・大码力・易部署 | Qwen3.6-27B上线魔乐社区，基于昇腾的部署教程来了

继一周前模型开源发布后，千问再度开源Qwen3.6-27B —— 一个拥有270亿参数的稠密多模态模型，也是社区呼声最高的模型规格。Qwen3.6-27B 依然支持多模态思考与非思考模式，在智能体编程方面达到了旗舰级表现，全面超越前代开源旗舰 Qwen3.5-397B-A17B（总参数397B / 激活参数17B的MoE模型）。作为稠密架构，它无需MoE路由即可部署，是开发者在实用、可广泛部署规模