Ruby实现的3种快速排序算法

发布时间：2020-12-16 22:51:54 所属栏目：百科来源：网络整理

导读：刚学Ruby，正巧算法老师鼓励用不熟悉的语言来写算法，我就用Ruby吧~~ 话说Ruby可真是超厉害，好多凭直觉的方法都可以用。。。。。无限膜拜中。。。。期间我遇到了invalid multibyte char (US-ASCII)的错误，解决办法是在开头加一个#encoding:utf-8 这个错误

刚学Ruby，正巧算法老师鼓励用不熟悉的语言来写算法，我就用Ruby吧~~
话说Ruby可真是超厉害，好多凭直觉的方法都可以用。。。。。无限膜拜中。。。。

期间我遇到了invalid multibyte char (US-ASCII)的错误，解决办法是在开头加一个#encoding:utf-8
这个错误在stackoverflow上有人问到过，某人给出的回答是
Write # encoding: utf-8 on top of that file. That changes the default encoding of all string/regexp literals in that file utf-8.
参考链接：http://stackoverflow.com/questions/3678172/ruby-1-9-invalid-multibyte-char-us-ascii

快速排序的普通版本：

复制代码代码如下:

#encoding: utf-8
#author: xu jin,4100213
#date: Oct 20,2012
#RandomizedQuickSort
#to sort an array by using QuickSort
#example:
#The original array is：[10,35,25,67,69,52,24,40,76,6,49]
#The sorted array is: [6,10,49,76]

arrayInt = Array.new
index = 0
while (index < 12)
arrayInt[index] = rand(100) #produce 12 random number
index += 1
end
puts "The original array is：" + arrayInt.to_s

def QuickSort(arrayInt,first,last)
if first < last
    middle = Partition(arrayInt,last)
    QuickSort(arrayInt,middle - 1)
    QuickSort(arrayInt,middle + 1,last)
end
end

def Partition(arrayInt,last)
x = arrayInt[last]
i = first - 1
for j in first .. (last - 1)
    if arrayInt[j] <= x
       i += 1
       arrayInt[i],arrayInt[j] = arrayInt[j],arrayInt[i] #exchange
    end
end
arrayInt[i + 1],arrayInt[last] = arrayInt[last],arrayInt[i + 1]
return i + 1
end

QuickSort(arrayInt,arrayInt.length-1)
puts "The sorted array is: " + arrayInt.to_s

快速排序的随机化版本：

复制代码代码如下:

#encoding: utf-8
#author: xu jin,2012
#RandomizedQuickSort
#to sort an array by using randomized QuickSort
#example:
#The original array is：[14,47,46,82,92,22,44,81,59,61]
#The sorted array is: [14,61,92]

arrayInt = Array.new
index = 0
while (index < 12)
arrayInt[index] = rand(100) #produce 12 random number
index += 1
end
puts "The original array is：" + arrayInt.to_s

def RandomizedQuickSort(arrayInt,last)
if first < last
    middle = RandomizedPartition(arrayInt,last)
    RandomizedQuickSort(arrayInt,middle - 1)
    RandomizedQuickSort(arrayInt,last)
end
end

def RandomizedPartition(arrayInt,last)
i = rand(last - first + 1) + first
arrayInt[i],arrayInt[i]
return Partition(arrayInt,last)
end

def Partition(arrayInt,arrayInt[i + 1]
return i + 1
end

RandomizedQuickSort(arrayInt,arrayInt.length-1)
puts "The sorted array is: " + arrayInt.to_s

快速排序的利用了Ruby的语法糖的随机化版本：

复制代码代码如下:

#encoding: utf-8
#author: xu jin,92]

arrayInt = Array.new
index = 0
while (index < 12)
arrayInt[index] = rand(100) #produce 12 random number
index += 1
end
puts "The original array is：" + arrayInt.to_s

def RandomizedQuickSort(a)
i = rand(a.length)
a[i],a[a.length - 1] = a[a.length - 1],a[i]
(x=a.pop) ? RandomizedQuickSort(a.select{|i| i <= x}) + [x] + RandomizedQuickSort(a.select{|i| i > x}) : []
end

puts "The sorted array is: " + RandomizedQuickSort(arrayInt).to_s

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!