Ruby 中的快速排序算法 - 堆栈级别太深

Question

我正在尝试用 Ruby 实现快速排序算法。我得到了一个简单的方法，工作得很快，但它涉及动态创建临时数组。我正在尝试实现一种更简化的快速排序，它仅在适当的位置交换元素，而不需要创建额外的数组。

有谁知道为什么这段代码不起作用？我一直在详细遵循here列出的模式，但我无法让它正常工作。

def quicksort(arr = [], left = 0, right = 0)
  right = arr.length - 1 if right < 1
  if left < right
    index = partition(arr, left, right)
    quicksort(arr, left, index - 1)
    quicksort(arr, index, right)
  end
  arr
end

def partition(arr, left, right)
  pivot = arr[(left + right) / 2]
  while left <= right
    left += 1 while arr[left] < pivot
    right -= 1 while arr[right] > pivot
    if left <= right
      arr[left], arr[right] = arr[right], arr[left]
      left += 1
      right -= 1
    end
  end
  left
end

arr = [8, 10, 13, 5, 6, 20, 2, 43, 9, 11, 15]
p quicksort(arr)

Answer 1

如果我们抛出调试

p "Left #{left}, Right #{right}

...

def quicksort(arr = [], left = 0, right = 0)
  right = arr.length - 1 if right < 1
  if left < right
    index = partition(arr, left, right)
    quicksort(arr, left, index - 1)
    ...

我们发现有问题。

left

从未设置。它始终是默认值 0。正确的是做自己的事情。

"Left 0, Right 10"
"Left 0, Right 8"
"Left 0, Right 2"
"Left 0, Right 1"
"Left 0, Right 10"
"Left 0, Right 7"
"Left 0, Right 6"
"Left 0, Right 5"
"Left 0, Right 2"
"Left 0, Right 1"
"Left 0, Right 10"
"Left 0, Right 4"
"Left 0, Right 2"
"Left 0, Right 1"
"Left 0, Right 10"
"Left 0, Right 5"
"Left 0, Right 2"
"Left 0, Right 1"
"Left 0, Right 10"
"Left 0, Right 5"
"Left 0, Right 2"
"Left 0, Right 1"

问题是

right = arr.length - 1 if right < 1

。如果

right

永远是 < 1 it's set back to the end of the array.

left

始终为 0，那么

left

始终小于

right

。

quicksort(arr, 0, index - 1)

一遍又一遍地递归。

quicksort(arr, index, right)

永远不会达到。

---

你的

partition

没问题，眼力好

pivot

可以在里面计算

pivot

。

让你陷入困境的是那些默认设置。只要

right

小于 1，您就可以为其设置默认值。但只有在根本未传入时才应设置它。

def quicksort(arr, left = 0, right = arr.length - 1)
  if left < right
    index = partition(arr, left, right)
    quicksort(arr, left, index - 1)
    quicksort(arr, index, right)
  end
  arr
end

现在

quicksort(array)

相当于

quicksort(array, 0, array.length - 1)

。后续递归调用会传入

left

和

right

，因此不需要默认值。

数组没有默认值。如果他们忘记传递一个数组，那应该是一个ArgumentError。

---

我更喜欢视频中使用的公共包装方法。如果有人不小心传递了太多参数，他们会得到一个明显的 ArgumentError，而不是发生奇怪的事情。

# Using the ! convention for functions which alter their arguments.
def quicksort!(array)
  _quicksort!(array, 0, array.length - 1)
end

private def _quicksort!(array, left, right)
  ...
end

Answer 2

如果对大型数组进行排序，堆栈空间可以限制为 O(log(n))，但最坏情况的时间复杂度将保持在 O(n^2)。我不知道 ruby 语法，但理想的是仅在较小的分区上递归，并循环返回较大的分区：

def quicksort(arr, left = 0, right = arr.length - 1)
  while left < right
    index = partition(arr, left, right)
    if((index - left) < (right-index))
        quicksort(arr, left, index - 1)
        left = index
    else
        quicksort(arr, index, right)
        right = index-1
  end
  arr
end

Answer 3

如果你想打印快速排序的每一步，你可以这样做：

def advanced_quicksort(arr, low = 0, high = arr.length - 1)
    if low < high
        pivot_index = partition(arr, low, high)
        puts "[#{arr.join(', ')}]" #you can change it to ```puts arr.join(' ') else
        advanced_quicksort(arr, low, pivot_index - 1)
        advanced_quicksort(arr, pivot_index + 1, high)
    end
end

def partition(arr, low, high)
    pivot = arr[high]
    i = low - 1

    (low..high - 1).each do |j|
        if arr[j] < pivot
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
        end
    end

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    i + 1
end

# Example usage:
arr = [1, 3, 9, 8, 2, 7, 5]
puts "[#{arr.join(', ')}]"
advanced_quicksort(arr)