堆棧級別太深，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