剛學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, 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

快速排序的隨機化版本：
代碼如下:
#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)