主页 > 知识库 > Ruby实现的3种快速排序算法

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

热门标签:语音系统 企业做大做强 电话运营中心 呼叫中心市场需求 百度AI接口 硅谷的囚徒呼叫中心 客户服务 Win7旗舰版

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

您可能感兴趣的文章:
  • Ruby实现的各种排序算法
  • ruby实现的插入排序和冒泡排序算法
  • Ruby实现的矩阵连乘算法
  • Ruby实现二分搜索(二分查找)算法的简单示例
  • Ruby实现的合并排序算法
  • Ruby实现的最优二叉查找树算法
  • Ruby实现的图片滤镜算法代码

标签:长沙 济南 崇左 安康 海南 山西 山西 喀什

巨人网络通讯声明:本文标题《Ruby实现的3种快速排序算法》,本文关键词  ;如发现本文内容存在版权问题,烦请提供相关信息告之我们,我们将及时沟通与处理。本站内容系统采集于网络,涉及言论、版权与本站无关。
  • 相关文章
  • 收缩
    • 微信客服
    • 微信二维码
    • 电话咨询

    • 400-1100-266