快速排序算法

Question

我的算法没有像预期的那样工作。当我使用起始值大于最后一个元素的数据集时，该方法按降序而不是升序对数字进行排序。我不确定更改输入和input.length -1处的数字是否可以将输出从升序改为反序。如果有任何关于如何解决这个问题的见解，我将不胜感激。谢谢!

def quickSort(input) 
divide = lambda do |first, last|
  if first >= last 
    return
  end 
  mid = first
  i = 0
  while i < last do
    if input[i] < input[last]
      input[i], input[mid] = input[mid], input[i]
      mid += 1
    end 
      i += 1
  end 
  input[mid], input[last] = input[last], input[mid]
  divide.call(first, mid - 1)
  divide.call(mid + 1, last)
end 
divide.call(0, input.length - 1 )
return input
end

quickSort([24, 6, 8, 2, 35]) // causes a descending sort
quickSort([3,9,1,4,7]) // works as intended

Answer 1

我不认为这是快速排序(至少不是我学到的方法)，如果您尝试将更多的值添加到第一个排序数组中，它将使程序崩溃。

看看下面的实现(我的ruby有点生疏了，请耐心听我说)

def quickSort(input)
  return input if input.length <= 1

  i = input.length - 1
  pivot = input[rand(i)]
  input.delete(pivot)
  lesser = []
  greater = []

  input.map do |n|
    lesser.push(n) if n < pivot
    greater.push(n) if n >= pivot
  end

  sorted = []
  sorted.concat(quickSort(lesser))
  sorted.push(pivot)
  sorted.concat(quickSort(greater))
  return sorted
end

print quickSort([24, 6, 8, 2, 35, 12])
puts ""
print quickSort([3,9,1,4,7,8,10,15,2])
puts ""

通常，在进行快速排序时，您将在数组中选择一个随机的枢轴，并将数组拆分为小于和大于枢轴的部分。然后递归地调用较小数组和较大数组上的快速排序，然后将它们重新联接到排序数组中。希望这能有所帮助！