神墓辰东小说,好看的小说君子以泽

主頁(yè) > 知識(shí)庫(kù) > Ruby實(shí)現(xiàn)的3種快速排序算法

Ruby實(shí)現(xiàn)的3種快速排序算法

剛學(xué)Ruby，正巧算法老師鼓勵(lì)用不熟悉的語(yǔ)言來(lái)寫算法，我就用Ruby吧~~
話說(shuō)Ruby可真是超厲害，好多憑直覺(jué)的方法都可以用。。。。。無(wú)限膜拜中。。。。

期間我遇到了invalid multibyte char (US-ASCII)的錯(cuò)誤，解決辦法是在開頭加一個(gè)#encoding:utf-8
這個(gè)錯(cuò)誤在stackoverflow上有人問(wèn)到過(guò)，某人給出的回答是
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

快速排序的普通版本：

復(fù)制代碼代碼如下:

#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, 69, 76, 6, 49]
#The sorted array is: [6, 10, 24, 25, 35, 40, 49, 52, 67, 69, 69, 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, first, last)
    QuickSort(arrayInt, first, middle - 1)
    QuickSort(arrayInt, middle + 1, last)
end
end

def Partition(arrayInt, first, 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, 0, arrayInt.length-1)
puts "The sorted array is: " + arrayInt.to_s

快速排序的隨機(jī)化版本：

復(fù)制代碼代碼如下:

#encoding: utf-8
#author: xu jin, 4100213
#date: Oct 20, 2012
#RandomizedQuickSort
#to sort an array by using randomized QuickSort
#example:
#The original array is：[14, 47, 46, 49, 82, 76, 92, 22, 44, 81, 59, 61]
#The sorted array is: [14, 22, 44, 46, 47, 49, 59, 61, 76, 81, 82, 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, first, last)
if first last
    middle = RandomizedPartition(arrayInt, first, last)
    RandomizedQuickSort(arrayInt, first, middle - 1)
    RandomizedQuickSort(arrayInt, middle + 1, last)
end
end

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

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

快速排序的利用了Ruby的語(yǔ)法糖的隨機(jī)化版本：

復(fù)制代碼代碼如下:

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

您可能感興趣的文章:

Ruby實(shí)現(xiàn)的各種排序算法
ruby實(shí)現(xiàn)的插入排序和冒泡排序算法
Ruby實(shí)現(xiàn)的矩陣連乘算法
Ruby實(shí)現(xiàn)二分搜索(二分查找)算法的簡(jiǎn)單示例
Ruby實(shí)現(xiàn)的合并排序算法
Ruby實(shí)現(xiàn)的最優(yōu)二叉查找樹算法
Ruby實(shí)現(xiàn)的圖片濾鏡算法代碼

標(biāo)簽：張家界遼寧永州梧州公主嶺三沙荊門普洱

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《Ruby實(shí)現(xiàn)的3種快速排序算法》，本文關(guān)鍵詞 Ruby,實(shí)現(xiàn),的,3種,快速,排序,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無(wú)關(guān)。

濮阳杆衣贸易有限公司

Ruby實(shí)現(xiàn)的3種快速排序算法