LSD基数排序整数

我在使用基数排序来处理一组固定长度的整数时遇到了麻烦。 在我下面的尝试实现最小有效数字基数排序，我有一个名为num_at函数返回数字num中的数字d。 我写的代码有w = 2，其中w代表每个数字的长度。 （本质上，然后，这个代码是为3位数字编写的，如下面的输入所示）。

我将此模型化为每个数字的按键索引计数，但是我得到了[0, 12, 32, 32, 44, 0] 0，12，32，32，44，0]的输出，坦白地说，为什么会有一段艰难的时间。 这是我的输入： [32,12,99,44,77, 12]我用99个值启动了count数组，因为根据键索引计数，所有可能的值可以在0到99之间。 这里有什么东西立即跳出来，因为不正确？ 另外，我的num_at方法是否是正确的方法，或者有更好的方法吗？

def num_at(num, d)
    return num if num/10 == 0 
    a = num 
    #return the dth digit of num
    counter = 0 
    until counter == d 
        a/=10 
        counter += 1 
    end 

    a % 10
end

def radix_sort(arr)
    w = 2
    #count_arr can have any possible number from 0-99
    aux = Array.new(arr.length) {0}

    d = w-1
    while d >= 0 
        count = Array.new(99) {0}
        i = 0 

        #create freq arr
        while i < arr.length 
            count[num_at(arr[i], d) + 1] += 1 #offset by 1 
            i += 1 
        end 

        #compute cumulates 
        i = 0 
        while i < count.length - 1
            count[i + 1] += count[i]
            i += 1
        end 

        z = 0 
        #populate aux arr
        while z < arr.length 
            aux[num_at(arr[z], d)] = arr[z]
            count[num_at(arr[z], d)] += 1 
            z += 1
        end

        #override original arr
        z = 0 
        while z < arr.length 
            arr[z] = aux[z]
            z += 1
        end 
        d -= 1
    end

    arr
end

这是从我试图用Ruby实现的教科书中取得的用于LSD基数排序的Java代码：

public static void lsd(String[] a)
{
 int N = a.length;
 int W = a[0].length;
 for (int d = W-1; d >= 0; d--)
 {
 int[] count = new int[R];
 for (int i = 0; i < N; i++)
 count[a[i].charAt(d) + 1]++;
 for (int k = 1; k < 256; k++)
 count[k] += count[k-1];
 for (int i = 0; i < N; i++)
 temp[count[a[i].charAt(d)]++] = a[i];
 for (int i = 0; i < N; i++)
 a[i] = temp[i];
 }

和密钥索引计数的伪代码（对每个字符重复）：

Task: sort an array a[] of N integers between 0 and R-1
Plan: produce sorted result in array temp[]
 1. Count frequencies of each letter using key as index
 2. Compute frequency cumulates
 3. Access cumulates using key as index to find record positions.
 4. Copy back into original array
 5. List item

LSD radix sort. Consider characters d from right to left  Stably sort
using dth character as the key via key-indexed counting.

上述Java代码/伪代码信息从此链接中获取：http://www.cs.princeton.edu/courses/archive/spring07/cos226/lectures/11RadixSort.pdf

链接地址: http://www.djcxy.com/p/70803.html

上一篇: LSD Radix Sort for Integers

下一篇: place" MSD radix sort, stack space, and Stack Overflow's