今天看啥
热点:

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


   这篇文章主要介绍了Ruby实现的3种快速排序算法,本文给出了快速排序的普通版本、快速排序的随机化版本、快速排序的利用了Ruby的语法糖的随机化版本三个版本,需要的朋友可以参考下

  刚学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)

  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

www.bkjia.comtruehttp://www.bkjia.com/ASPjc/1004487.htmlTechArticleRuby实现的3种快速排序算法 这篇文章主要介绍了Ruby实现的3种快速排序算法,本文给出了快速排序的普通版本、快速排序的随机化版本、快速...

相关文章

    暂无相关文章
相关搜索:

帮客评论

视觉看点