剛學(xué)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
快速排序的普通版本：
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
快速排序的隨機化版本：
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
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
RandomizedQuickSort(arrayInt, 0, arrayInt.length-1)
puts "The sorted array is: " + arrayInt.to_s
快速排序的利用了Ruby的語法糖的隨機化版本：
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
新聞熱點
疑難解答
圖片精選
