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

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

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

快速排序的普通版本：

#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)
    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的语法糖的随机化版本：

#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(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