哪里建设品牌网站,mip织梦手机网站模板,网站模板之家,泗洪房产网快速排序#xff08;Quick Sort#xff09;
快速排序是一种高效的排序算法#xff0c;采用分治法#xff08;Divide and Conquer#xff09;策略。它的基本思想是#xff1a;选择一个基准元素#xff08;pivot#xff09;#xff0c;将数组分为两部分#xff0c;使得…快速排序Quick Sort
快速排序是一种高效的排序算法采用分治法Divide and Conquer策略。它的基本思想是选择一个基准元素pivot将数组分为两部分使得左边部分的元素都小于基准元素右边部分的元素都大于基准元素然后递归地对左右两部分进行排序。
快速排序的步骤
选择基准元素从数组中选择一个元素作为基准通常选择第一个、最后一个或中间元素。分区操作将数组分为两部分左边部分的元素小于基准元素右边部分的元素大于基准元素。递归排序对左右两部分递归地应用快速排序。合并结果由于分区操作已经保证了左边部分小于右边部分最终数组自然有序。
时间复杂度
最坏情况O(n²) —— 当每次选择的基准元素都是最小或最大元素时。最好情况O(n log n) —— 当每次选择的基准元素都能将数组均匀分为两部分时。平均情况O(n log n)
空间复杂度
O(log n) —— 递归调用栈的深度。 Python 实现
def quick_sort(arr):if len(arr) 1:return arrpivot 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 quick_sort(left) middle quick_sort(right) # 递归排序并合并# 示例使用
arr [3, 6, 8, 10, 1, 2, 1]
sorted_arr quick_sort(arr)
print(排序后的数组:, sorted_arr)输出结果
排序后的数组: [1, 1, 2, 3, 6, 8, 10]快速排序的详细过程
以数组 [3, 6, 8, 10, 1, 2, 1] 为例 第一轮 选择基准元素 10假设选择最后一个元素。分区结果 左边部分[3, 6, 8, 1, 2, 1]右边部分[] 递归排序左边部分。 第二轮 选择基准元素 1左边部分的最后一个元素。分区结果 左边部分[]右边部分[3, 6, 8, 2] 递归排序右边部分。 第三轮 选择基准元素 2右边部分的最后一个元素。分区结果 左边部分[]右边部分[3, 6, 8] 递归排序右边部分。 第四轮 选择基准元素 8右边部分的最后一个元素。分区结果 左边部分[3, 6]右边部分[] 递归排序左边部分。 第五轮 选择基准元素 6左边部分的最后一个元素。分区结果 左边部分[3]右边部分[] 递归排序左边部分。 合并结果 最终排序结果为 [1, 1, 2, 3, 6, 8, 10]。 快速排序的优缺点
优点
平均时间复杂度为 O(n log n)性能优异。是原地排序算法不需要额外的存储空间。在实际应用中表现良好是常用的排序算法之一。
缺点
最坏情况下时间复杂度为 O(n²)但可以通过优化基准选择策略来避免。不是稳定的排序算法相同元素的相对位置可能改变。 优化快速排序 随机选择基准元素 避免最坏情况的发生提高算法的稳定性。 三数取中法 选择第一个、最后一个和中间元素的中位数作为基准。 小数组使用插入排序 当数组规模较小时插入排序的效率更高。 优化后的快速排序实现
import randomdef quick_sort_optimized(arr):if len(arr) 1:return arrpivot random.choice(arr) # 随机选择基准元素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 quick_sort_optimized(left) middle quick_sort_optimized(right)# 示例使用
arr [3, 6, 8, 10, 1, 2, 1]
sorted_arr quick_sort_optimized(arr)
print(优化后的排序数组:, sorted_arr)总结
快速排序是一种高效的排序算法适用于大规模数据的排序。通过优化基准选择策略可以进一步提高其性能和稳定性。
