为什么要测试quicksort算法中的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语句并查看会发生什么）。在快速排序的情况下，基本情况是当您尝试对一个范围为空或仅包含一个数字的数字进行排序时，这种情况下您无需执行任何操作。