下面是我在Ruby中实现快速排序的方法：

def quicksort(*ary)
  return [] if ary.empty?

  pivot = ary.delete_at(rand(ary.size))
  left, right = ary.partition(&pivot.method(:>))

  return *quicksort(*left), pivot, *quicksort(*right)
end

实际上，我可能会将它改为Array的示例方法：

class Array
  def quicksort
    return [] if empty?

    pivot = delete_at(rand(size))
    left, right = partition(&pivot.method(:>))

    return *left.quicksort, pivot, *right.quicksort
  end
end

下面是一个（非常）简单的快速排序实现，它基于维基百科的简单快速排序伪代码：

def quicksort(array) #takes an array of integers as an argument

您需要一个基本情况，否则递归调用永远不会终止

if array.length <= 1
  return array

现在选择一个轴：

else
  pivot = array.sample
  array.delete_at(array.index(pivot)) # remove the pivot
  #puts "Picked pivot of: #{pivot}"
  less = []
  greater = []

循环遍历数组，比较要透视的项，并将它们收集到less和greater数组中。

array.each do |x|
    if x <= pivot
      less << x
    else
      greater << x
    end
  end

现在，在less和greater数组上递归调用quicksort()。

sorted_array = []
  sorted_array << self.quicksort(less)
  sorted_array << pivot
  sorted_array << self.quicksort(greater)

返回sorted_array，就完成了。

# using Array.flatten to remove subarrays
  sorted_array.flatten!

您可以使用

qs = QuickSort.new

puts qs.quicksort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5] # true
puts qs.quicksort([5]) == [5] # true
puts qs.quicksort([5, -5, 11, 0, 3]) == [-5, 0, 3, 5, 11] # true
puts qs.quicksort([5, -5, 11, 0, 3]) == [5, -5, 11, 0, 3] # false

这是另一种实现quicksort的方法--作为新手，我认为它更容易理解--希望它能帮助到别人：）在这个实现中，pivot总是数组中的最后一个元素--我遵循Khan Academy course，这就是我得到灵感的地方

def quick_sort(array, beg_index, end_index)
  if beg_index < end_index
    pivot_index = partition(array, beg_index, end_index)
    quick_sort(array, beg_index, pivot_index -1)
    quick_sort(array, pivot_index + 1, end_index)
  end
  array
end

#returns an index of where the pivot ends up
def partition(array, beg_index, end_index)
  #current_index starts the subarray with larger numbers than the pivot
  current_index = beg_index
  i = beg_index
  while i < end_index do
    if array[i] <= array[end_index]
      swap(array, i, current_index)
      current_index += 1
    end
    i += 1
  end
  #after this swap all of the elements before the pivot will be smaller and
  #after the pivot larger
  swap(array, end_index, current_index)
  current_index
end

def swap(array, first_element, second_element)
  temp = array[first_element]
  array[first_element] = array[second_element]
  array[second_element] = temp
end

puts quick_sort([2,3,1,5],0,3).inspect #will return [1, 2, 3, 5]

我的实现基于Grokking-Algorithms book的递归算法：

def quick_sort(arr)
  return arr if arr.size < 2

  pivot = arr[0]
  less = arr[1..].select {|el| el <= pivot}
  greater = arr[1..].select {|el| el > pivot}
  return *quick_sort(less), pivot, *quick_sort(greater)
end

def sort(ary)
  return ary if ary.size < 2

  pivot = ary[-1]
  sm_ary = []
  lg_ary = []

  ary[0..-2].each do |x|
    lg_ary.push(x) && next if x >= pivot

    sm_ary.push(x) && next if x < pivot
  end

  [*sort(sm_ary), pivot, *sort(lg_ary)]
end

arr = [10, 7, 8, 9, 7, 1, 5]
print sort(arr) 
# [1, 5, 7, 7, 8, 9, 10]

def quicksort(array)
  # if array is empty or has only one element there is no need to sort
  return array if array.size <= 1 
  
  # for the sake of performance (ms performance :] ) we can always use the first element as a pivot
  pivot = array.delete_at(0) 

  # partition will split array into 2 sub arrays based on the condition passed
  # in this case everything smaller than the pivot will be the first array on the left => [[ e < pivot ], [e > pivot]]
  # the e qual to pivot will go on the bigger element 
  left, right = array.partition { |e| e < pivot } 

  # flatten the multiple sub arrays returned from recursive quicksorts
  return [quicksort(left), pivot, quicksort(right)].flatten 
end