用Ruby语言快速排序

我试图在ruby中实现快速排序，但是在第一个pivot分区之后陷入了如何以递归方式调用的问题。 请帮助我了解如何继续，并让我知道我的编码风格到目前为止是否良好。

class QuickSort $array= Array.new() $count=0 def add(val) #adding values to sort i=0 while val != '000'.to_i $array[i]= val.to_i i=i+1 val = gets.to_i end end def firstsort_aka_divide(val1,val2,val3) #first partition $count = $count+1 @pivot = val1 @left = val2 @right =val3 while @left!=@right do # first divide/ partition logic if $array[@right] > $array[@pivot] then @right= @right-1 elsif $array[@right] < $array[@pivot] then @var = $array[@right] $array[@right] = $array[@pivot] $array[@pivot] = @var @pivot = @right @left = @left+1 end if $array[@left]  $array[@pivot] @var = $array[@left] $array[@left] = $array[@pivot] $array[@pivot] = @var @pivot =@left end end puts "\n" # printing after the first partition ie divide print " Array for for divide ---> #{$array}" puts "\n" puts " pivot,left,right after first divide --> #{@pivot},#{@left},#{@right}" firstsort_aka_divide() # Have to call left side of partition recursively -- need help firstsort_aka_divide() # Have to call right side of partition recursively -- need help end end ob= QuickSort.new puts " Enter the numbers you want to sort. \n Press '000' once you are done entering the values" val = gets.to_i ob.add(val) puts " Sorting your list ..." sleep(2) ob.firstsort_aka_divide(0,0,($array.size-1)) # base condition for partitioning 

Answer 1

这是一个（非常）天真的quicksort实现，基于Wikipedia的简单快速排序伪代码 ：

 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 = [] 

循环遍历数组，将项目与pivot进行比较，并将它们收集到less数组中。

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

现在，递归地在less数组上调用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 

Answer 2

这就是我在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 

Answer 3

这是实现快速排序的另一种方式 – 作为一个新手，我认为它更容易理解 – 希望它有助于某人:)在这个实现中，数据透视图始终是数组中的最后一个元素 – 我正在遵循可汗学院课程和这就是我从中获得灵感的地方

 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]