1. 定位导航前面已经学习了随机算法的基本思想随机性不是碰运气而是用来降低坏情况稳定发生的概率。快速排序正是随机化思想非常典型的应用。它本身是分治算法划分数组 → 递归处理左右部分 → 得到有序结果随机化的地方在于每次划分前随机选择主元。2. 概念术语术语定义举例主元用来划分数组的元素pivot 6划分把数组分成小于主元和大于主元的部分[1,2,3] [6] [9,8,7]随机主元从当前区间随机选择主元随机选下标均衡划分左右子数组规模接近一半一半不均衡划分一边很大一边很小0 和 n-1期望时间多次随机运行的平均时间平均O(n log n)原地排序主要在原数组上操作经典快速排序可原地实现关键澄清随机化快速排序最终结果仍然正确。随机的是执行路径不是排序结果。随机主元不是保证每次最好而是降低连续最差的概率。快速排序平均表现好但最坏情况仍可能是O(n²)。3. 快速排序的核心流程快速排序可以分成四步核心逻辑是1. 选择一个主元 pivot 2. 把小于 pivot 的元素放左边 3. 把大于 pivot 的元素放右边 4. 递归排序左右两边当左右子数组都变成有序后整个数组自然有序。4. 为什么固定主元可能很危险如果每次都固定选择第一个元素作为主元那么某些输入会非常不友好。例如输入已经有序[1, 2, 3, 4, 5, 6, 7]如果每次都选第一个元素划分可能变成左边为空右边有 n-1 个元素这种划分非常不均衡。递归树会接近一条链而不是一棵平衡树。如果每一层都只减少一个元素递归深度会接近n总成本可能退化到O(n2) O(n^2)O(n2)5. 随机化快速排序怎么做随机化快速排序只改一个关键点主元不固定选而是随机选。例如当前数组是[9, 1, 8, 2, 7, 3, 6]随机选到主元6后可以划分为得到小于 6[1, 2, 3] 主元 6[6] 大于 6[9, 8, 7]接下来只需要递归处理左右两边。6. 动态推演随机化快速排序过程下面用动态图看完整过程。过程可以概括为当前数组准备划分随机选择一个主元根据主元划分左右两边递归处理左侧递归处理右侧合并得到最终有序结果。这里的“合并”不像归并排序那样需要额外线性合并因为划分后主元已经在正确位置左右两边分别排好后整体自然有序。7. 为什么平均表现很好快速排序好不好关键看划分是否均衡。如果每次都接近一半一半递归树高度大约是O(logn) O(\\log n)O(logn)每层划分总成本大约是O(n) O(n)O(n)所以总成本接近O(nlogn) O(n \\log n)O(nlogn)随机化的意义在于不保证每次都均衡但连续极端不均衡的概率很低。因此随机化快速排序通常关注期望运行时间O(nlogn) O(n \\log n)O(nlogn)8. 复杂度分析快速排序常见复杂度可以这样记情况说明复杂度最好情况每次划分都很均衡O(n log n)平均情况随机主元下的期望表现O(n log n)最坏情况每次都极端不均衡O(n²)空间复杂度递归栈深度平均O(log n)最坏O(n)要注意随机化并没有消除最坏情况只是让最坏情况不容易稳定发生。这就是随机化快速排序的核心价值。9. 代码实践下面给出一个直观版本的随机化快速排序。importrandomdefrandomized_quick_sort(nums):iflen(nums)1:returnnums[:]pivotrandom.choice(nums)less[]equal[]greater[]forxinnums:ifxpivot:less.append(x)elifxpivot:greater.append(x)else:equal.append(x)returnrandomized_quick_sort(less)equalrandomized_quick_sort(greater)if__name____main__:nums[9,1,8,2,7,3,6]print(randomized_quick_sort(nums))输出[1, 2, 3, 6, 7, 8, 9]上面这个版本更容易理解但不是原地实现。如果追求空间效率可以使用原地 partition但代码会更复杂。原地版本示例importrandomdefpartition(arr,left,right):pivot_indexrandom.randint(left,right)arr[pivot_index],arr[right]arr[right],arr[pivot_index]pivotarr[right]ileft-1forjinrange(left,right):ifarr[j]pivot:i1arr[i],arr[j]arr[j],arr[i]arr[i1],arr[right]arr[right],arr[i1]returni1defquick_sort(arr,left,right):ifleftright:pivot_pospartition(arr,left,right)quick_sort(arr,left,pivot_pos-1)quick_sort(arr,pivot_pos1,right)nums[9,1,8,2,7,3,6]quick_sort(nums,0,len(nums)-1)print(nums)10. 常见误区误区一随机化后就没有最坏情况不对。最坏情况仍然存在只是发生概率被降低了。误区二随机主元一定比固定主元快不一定。单次运行可能更快也可能更慢。随机化关注的是长期平均表现和抗坏输入能力。误区三快速排序一定稳定不是。经典快速排序通常不是稳定排序。如果相等元素的相对顺序需要保持需要使用其他策略。误区四递归实现不用考虑栈深度不对。最坏情况下递归深度可能达到O(n)工程实现中常会做尾递归优化、深度限制或切换到其他排序。11. 现代延伸工程中的排序实现往往不是单一算法而是混合策略。常见做法包括优化策略作用随机主元降低坏输入稳定触发最坏情况的概率三数取中更稳健地选择主元小数组切换插入排序降低常数成本递归深度限制防止栈过深退化时切换堆排序避免最坏情况不可控很多高性能排序实现都会综合这些策略。这说明一个重要事实理论复杂度很重要但工程实现还要考虑常数、内存、递归深度和坏输入防护。12. 思考题快速排序为什么属于分治算法为什么固定选择第一个元素作为主元可能很危险随机主元为什么能降低坏情况稳定发生的概率随机化快速排序的平均复杂度是多少最坏复杂度是多少为什么工程排序实现常常会混合多种排序算法13. 本篇小结本篇讲清楚了随机化快速排序。核心结论是快速排序通过主元划分数组再递归排序左右两边主元选择会影响划分是否均衡固定主元可能被特殊输入触发最坏情况随机主元可以降低连续坏划分发生的概率随机化快速排序平均运行时间通常是O(n log n)最坏情况仍然可能是O(n²)工程实现中常结合随机化、插入排序、深度限制等策略。一句话总结随机化快速排序不是保证每次都最好而是避免总是最坏。
算法基础（十四）—— 随机化快速排序为什么平均表现很好
1. 定位导航前面已经学习了随机算法的基本思想随机性不是碰运气而是用来降低坏情况稳定发生的概率。快速排序正是随机化思想非常典型的应用。它本身是分治算法划分数组 → 递归处理左右部分 → 得到有序结果随机化的地方在于每次划分前随机选择主元。2. 概念术语术语定义举例主元用来划分数组的元素pivot 6划分把数组分成小于主元和大于主元的部分[1,2,3] [6] [9,8,7]随机主元从当前区间随机选择主元随机选下标均衡划分左右子数组规模接近一半一半不均衡划分一边很大一边很小0 和 n-1期望时间多次随机运行的平均时间平均O(n log n)原地排序主要在原数组上操作经典快速排序可原地实现关键澄清随机化快速排序最终结果仍然正确。随机的是执行路径不是排序结果。随机主元不是保证每次最好而是降低连续最差的概率。快速排序平均表现好但最坏情况仍可能是O(n²)。3. 快速排序的核心流程快速排序可以分成四步核心逻辑是1. 选择一个主元 pivot 2. 把小于 pivot 的元素放左边 3. 把大于 pivot 的元素放右边 4. 递归排序左右两边当左右子数组都变成有序后整个数组自然有序。4. 为什么固定主元可能很危险如果每次都固定选择第一个元素作为主元那么某些输入会非常不友好。例如输入已经有序[1, 2, 3, 4, 5, 6, 7]如果每次都选第一个元素划分可能变成左边为空右边有 n-1 个元素这种划分非常不均衡。递归树会接近一条链而不是一棵平衡树。如果每一层都只减少一个元素递归深度会接近n总成本可能退化到O(n2) O(n^2)O(n2)5. 随机化快速排序怎么做随机化快速排序只改一个关键点主元不固定选而是随机选。例如当前数组是[9, 1, 8, 2, 7, 3, 6]随机选到主元6后可以划分为得到小于 6[1, 2, 3] 主元 6[6] 大于 6[9, 8, 7]接下来只需要递归处理左右两边。6. 动态推演随机化快速排序过程下面用动态图看完整过程。过程可以概括为当前数组准备划分随机选择一个主元根据主元划分左右两边递归处理左侧递归处理右侧合并得到最终有序结果。这里的“合并”不像归并排序那样需要额外线性合并因为划分后主元已经在正确位置左右两边分别排好后整体自然有序。7. 为什么平均表现很好快速排序好不好关键看划分是否均衡。如果每次都接近一半一半递归树高度大约是O(logn) O(\\log n)O(logn)每层划分总成本大约是O(n) O(n)O(n)所以总成本接近O(nlogn) O(n \\log n)O(nlogn)随机化的意义在于不保证每次都均衡但连续极端不均衡的概率很低。因此随机化快速排序通常关注期望运行时间O(nlogn) O(n \\log n)O(nlogn)8. 复杂度分析快速排序常见复杂度可以这样记情况说明复杂度最好情况每次划分都很均衡O(n log n)平均情况随机主元下的期望表现O(n log n)最坏情况每次都极端不均衡O(n²)空间复杂度递归栈深度平均O(log n)最坏O(n)要注意随机化并没有消除最坏情况只是让最坏情况不容易稳定发生。这就是随机化快速排序的核心价值。9. 代码实践下面给出一个直观版本的随机化快速排序。importrandomdefrandomized_quick_sort(nums):iflen(nums)1:returnnums[:]pivotrandom.choice(nums)less[]equal[]greater[]forxinnums:ifxpivot:less.append(x)elifxpivot:greater.append(x)else:equal.append(x)returnrandomized_quick_sort(less)equalrandomized_quick_sort(greater)if__name____main__:nums[9,1,8,2,7,3,6]print(randomized_quick_sort(nums))输出[1, 2, 3, 6, 7, 8, 9]上面这个版本更容易理解但不是原地实现。如果追求空间效率可以使用原地 partition但代码会更复杂。原地版本示例importrandomdefpartition(arr,left,right):pivot_indexrandom.randint(left,right)arr[pivot_index],arr[right]arr[right],arr[pivot_index]pivotarr[right]ileft-1forjinrange(left,right):ifarr[j]pivot:i1arr[i],arr[j]arr[j],arr[i]arr[i1],arr[right]arr[right],arr[i1]returni1defquick_sort(arr,left,right):ifleftright:pivot_pospartition(arr,left,right)quick_sort(arr,left,pivot_pos-1)quick_sort(arr,pivot_pos1,right)nums[9,1,8,2,7,3,6]quick_sort(nums,0,len(nums)-1)print(nums)10. 常见误区误区一随机化后就没有最坏情况不对。最坏情况仍然存在只是发生概率被降低了。误区二随机主元一定比固定主元快不一定。单次运行可能更快也可能更慢。随机化关注的是长期平均表现和抗坏输入能力。误区三快速排序一定稳定不是。经典快速排序通常不是稳定排序。如果相等元素的相对顺序需要保持需要使用其他策略。误区四递归实现不用考虑栈深度不对。最坏情况下递归深度可能达到O(n)工程实现中常会做尾递归优化、深度限制或切换到其他排序。11. 现代延伸工程中的排序实现往往不是单一算法而是混合策略。常见做法包括优化策略作用随机主元降低坏输入稳定触发最坏情况的概率三数取中更稳健地选择主元小数组切换插入排序降低常数成本递归深度限制防止栈过深退化时切换堆排序避免最坏情况不可控很多高性能排序实现都会综合这些策略。这说明一个重要事实理论复杂度很重要但工程实现还要考虑常数、内存、递归深度和坏输入防护。12. 思考题快速排序为什么属于分治算法为什么固定选择第一个元素作为主元可能很危险随机主元为什么能降低坏情况稳定发生的概率随机化快速排序的平均复杂度是多少最坏复杂度是多少为什么工程排序实现常常会混合多种排序算法13. 本篇小结本篇讲清楚了随机化快速排序。核心结论是快速排序通过主元划分数组再递归排序左右两边主元选择会影响划分是否均衡固定主元可能被特殊输入触发最坏情况随机主元可以降低连续坏划分发生的概率随机化快速排序平均运行时间通常是O(n log n)最坏情况仍然可能是O(n²)工程实现中常结合随机化、插入排序、深度限制等策略。一句话总结随机化快速排序不是保证每次都最好而是避免总是最坏。
