堆栈级别太深，quicksort实现

Question

我想在ruby中实现quicksort算法，但是当我调用方法时，我当前遇到“堆栈级别太深”的错误。我认为它与无限循环有关，但我无法找到发生这种情况的位置，因为据我所知，确实指定了一个basecase。

我的代码如下：

def partition(array, left, right) 
    pivot = array[right] 
    p_index = left 
    for i in left..right 
     if array[i] <= pivot 
      array[i], array[p_index] = array[p_index], array[i] 
      p_index += 1 
     end 
    end 
    return p_index 
end 

def quick_sort(array, left, right) 
    if left < right 
     return array if array.length <= 1 
     q = partition(array, left, right) 
     quick_sort(array, left, q - 1) 
     quick_sort(array, q + 1, right) 
    end 
end 

Answer 1

的错误是在下面一行在quick_sort功能：

return array if array.length <= 1 

这不会是真的为array.length总是会大于1，

我想你打算做

return array if right - left <= 1