示例代码纯粹是为了加深印象，选择的目标语言有更便捷的实现方式，另外去掉了一些假设条件检查。
#encoding:gbk
NElement = 20
NRadix = 4
K = 5
arr = Array.new(NElement) do #初始化待排序数组，随机填写元素
Array.new(NRadix) do
rand(K)
end
end
def counting_sort(a,b,r,k)
c = Array.new(k + 1,0) #下标数组
a.each do |x|
c[x[r]] += 1 #计数
end
c.each_with_index do |x,i|
next if i == 0
c[i] += c[i - 1] #累计计数
end
a.reverse.each do |x|
function(){ //K线图 http://www.kaifx.cn/mt4/kaifx/1770.html
b[c[x[r]] - 1] = x #放置元素
c[x[r]] -= 1 #为相同输入挪动下标，这里是往前挪，所以在基数排序中多次排序需逆向输入元素
end
end
def radix_sort(a,r,k)
b = Array.new(a.size,nil)
(r - 1).downto 0 do |ri|
counting_sort(a,b,ri,k)
a = b
end
b
end
a = arr.clone #输入数组
b = radix_sort(a,NRadix,K)
arr.each do |x|
puts x.inspect
end
puts '-'*10
b.each do |x|
puts x.inspect
End
输出如下：
---------- Ruby ----------
[2, 4, 3, 3]
[2, 3, 4, 0]
[1, 0, 3, 3]
[3, 1, 0, 2]
[2, 2, 3, 1]
[2, 0, 0, 0]
[4, 2, 3, 1]
[1, 1, 2, 3]
[2, 0, 2, 0]
[1, 0, 0, 3]
[4, 2, 1, 0]
[4, 3, 2, 2]
[2, 0, 2, 1]
[1, 0, 4, 3]
[0, 2, 2, 0]
[1, 2, 0, 2]
[1, 0, 1, 1]
[4, 0, 2, 3]
[1, 2, 0, 1]
[1, 1, 3, 3]
----------
[0, 2, 2, 0]
[1, 0, 0, 3]
[1, 0, 1, 1]
[1, 0, 3, 3]
[1, 0, 4, 3]
[1, 1, 2, 3]
[1, 1, 3, 3]
[1, 2, 0, 1]
[1, 2, 0, 2]
[2, 0, 0, 0]
[2, 0, 2, 0]
[2, 0, 2, 1]
[2, 2, 3, 1]
[2, 3, 4, 0]
[2, 4, 3, 3]
[3, 1, 0, 2]
[4, 0, 2, 3]
[4, 2, 1, 0]
[4, 2, 3, 1]
[4, 3, 2, 2]
Output completed (0 sec consumed) - Normal Termination |
|
收藏
淘帖
踩
