Ruby   发布时间:2022-04-03  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了用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]
                @left= @left+1
            elsif $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 i.e 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,($array.size-1)) # base condition for partitioning

解决方法

这是一个基于 Wikipedia’s simple-quicksort pseudocode的(非常)天真的快速实施方案:
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进行比较,并将它们收集到越来越多的数组中.

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

现在,递归地在越来越少的数组上调用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,5] # true
puts qs.quicksort([5]) == [5] # true
puts qs.quicksort([5,-5,11,3]) == [-5,5,11] # true
puts qs.quicksort([5,3]) == [5,3] # false

大佬总结

以上是大佬教程为你收集整理的用Ruby语言快速排序全部内容,希望文章能够帮你解决用Ruby语言快速排序所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。