快速排序递归实现：如何按要求输出中间分区过程？

我正在完成学校的快速排序编程练习，已经实现了基础分区功能：给定数组array，以首个元素为pivot，将小于pivot的元素放在左侧、大于的放在右侧，且保留原有相对顺序，输出分区后的数组。对应的Ruby代码如下：

def partition(array)
  pivot = array.shift()
  base = [pivot]
  left = []
  right = []
  array.each do |e|
    if e < pivot
      left.push(e)
    else
      right.push(e)
    end
  end
  left + base + right
end

p partition([4, 5, 3, 9, 1])
# => [3, 1, 4, 5, 9]

新任务要求 #

现在需要递归调用上述分区逻辑，并按指定格式输出中间过程。示例输入[5, 8, 1, 3, 7, 10, 2]的预期输出为：

2 3
1 2 3
7 8 10
1 2 3 5 7 8 10

我能完成数组排序，但无法满足中间步骤的输出格式要求，尝试了多种代码仍未解决：

尝试1（pivot设为末尾元素） #

def partition(array)
    pivot = array[-1]
    i = -1
    j = 0
    while j < array.length-1
        if array[j] < pivot
            i += 1
            array[i], array[j] = array[j], array[i]
        end
        j += 1
    end
    array.insert(i+1, array.pop)
    puts index = i+1
    puts (array.take index).join(' ')
    puts (array.drop index+1).join(' ')
end

partition([5, 8, 1, 3, 7, 10, 2])

尝试2（递归终止条件问题） #

def partition(array)
    pivot = array.shift()
    base = [pivot]
    left = []
    right = []
    array.each do |e|
      if e < pivot
        left.push(e)
      else
        right.push(e)
      end
    end
    left + base + right
    if left.length < 2
      return
    end
    partition(left)
end

p partition([5, 8, 1, 3, 7, 10, 2])
p partition([1, 3, 2])
p partition([8, 7, 10])

解决方案 #

要实现要求的中间步骤输出，需要在递归排序的过程中，每当完成一个子数组的排序（即子数组长度≥2时），就输出该子数组的结果。同时注意递归顺序：先处理左子数组，再处理右子数组，最后输出整个排序后的数组。

以下是符合要求的代码：

def quicksort_with_steps(array)
  # 递归终止条件：数组长度小于2无需排序
  return array if array.length < 2

  pivot = array.shift
  left = []
  right = []

  array.each do |e|
    e < pivot ? left.push(e) : right.push(e)
  end

  # 递归处理左右子数组
  sorted_left = quicksort_with_steps(left)
  sorted_right = quicksort_with_steps(right)

  # 合并结果
  sorted_array = sorted_left + [pivot] + sorted_right

  # 输出中间步骤：仅当当前处理的数组长度≥2时输出
  puts sorted_array.join(' ') if sorted_array.length >= 2

  sorted_array
end

# 调用示例
quicksort_with_steps([5, 8, 1, 3, 7, 10, 2])

代码说明 #

1. 递归逻辑：每次将数组分为左、pivot、右三部分，递归排序左右子数组后合并。
2. 中间输出时机：在合并得到当前子数组的排序结果后，若子数组长度≥2，则输出该数组。这样会先输出左子树的排序结果，再输出右子树的，最后输出整个数组，完全匹配示例的输出顺序。
3. 保留相对顺序：沿用了你最初的分区逻辑，保证小于pivot的元素相对顺序不变。

运行上述代码，输入[5, 8, 1, 3, 7, 10, 2]会得到预期输出：

2 3
1 2 3
7 8 10
1 2 3 5 7 8 10

内容的提问来源于stack exchange，提问作者PRATAP-PANABAKA