algorithm - 为什么我们在快速排序算法中测试 if lo < hi？

Question

算法如下:

sort(A)
  quicksort(A, 0, n-1)
end

quicksort(A, lo, hi)
  if lo < hi then
    pi = partition(A, lo, hi)
    quicksort(A, lo, pi-1)
    quicksort(A, pi+1, hi)
end

我的问题是，为什么 lo < hi 是先决条件？

Answer 1

每个递归函数都需要一个基本情况:一个或多个(组)参数值，可以直接返回答案而不是再次递归。否则，递归将无限地进行(或者在实践中，直到您用完堆栈内存 - 尝试删除 if 语句，看看会发生什么)。在快速排序的情况下，基本情况是当您尝试对一系列为空或仅包含一个数字的数字进行排序时，在这种情况下您不需要执行任何操作。