算法回锅肉排序

示例代码纯粹是为了加深印象,选择的目标语言有更便捷的实现方式,另外去掉了一些假设条件检查。

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...
                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

评论

暂无评论