为何quick_sort函数需两次递归调用？疑惑第二个递归语句不可达

首先得明确快速排序的核心逻辑是分治思想：把一个大数组拆成两个子数组，分别排序后整个数组就有序了。所以两次递归分别对应排序基准左边的子数组和右边的子数组，这是算法的必然要求。

至于你觉得最后一行递归quick_sort(array, pi + 1, high)执行不了，是对递归的执行流程理解有偏差——递归调用并不会直接终止当前函数，而是去执行新的函数实例，等这个子递归完全执行完毕（所有嵌套的递归都返回），程序会回到当前函数的调用点，继续往下执行后续代码。

我们结合代码一步步看执行流程：

# 快速排序函数
def quick_sort(array, low, high):
  if low < high:
      # 找到基准元素的位置pi，此时pi左侧元素均<=基准，右侧均>=基准
      pi = partition(array, low, high)
      
      # 第一次递归：排序基准左侧的子数组[low, pi-1]
      quick_sort(array, low, pi - 1)
      
      # 等上面的递归完全执行完（左半部分排好序），才会执行这一行
      # 第二次递归：排序基准右侧的子数组[pi+1, high]
      quick_sort(array, pi + 1, high)

举个具体的小例子帮助理解：
假设我们排序数组[3,1,4,2]，第一次调用quick_sort时low=0，high=3，满足low<high：

1. 经过partition后，基准3的位置pi=2，此时数组变成[1,2,3,4]；
2. 先执行左递归quick_sort(array, 0, 1)，这个子递归会处理[1,2]：
   • 在这个子递归里，low=0 < high=1，执行partition得到pi=0（基准是1）；
   • 调用左递归quick_sort(array, 0, -1)，此时low>high，直接返回；
   • 回到子递归，执行右递归quick_sort(array, 1, 1)，low=high，直接返回；
   • 至此左半部分的递归完全结束，回到最开始的函数调用点；
3. 现在才会执行最后一行的右递归quick_sort(array, 3, 3)，此时low=high，直接返回；
4. 整个排序完成。

简单说：第一次递归是处理左半区，处理完回来再处理右半区，两次递归是分治思想的体现，缺一不可——少了任意一次，都会有一半的数组没被排序。

内容的提问来源于stack exchange，提问作者Kumail Raza