基数排序数字比较

Question

我有一个 LSD 基数排序算法的实现，想知道在排序过程中如何计算数字比较的次数？我知道该算法不是基于比较的，但是算法排序的整数元素的数字之间仍然存在某种比较。有人可以指出比较发生在哪里吗？

谢谢！

LSDRadixSort:

public static void lsdRadixSort(int[] a)
{
    final int BITS = 32; // each int is 32 bits 
    final int R = 1 << BITS_PER_BYTE; // each bytes is between 0 and 255
    final int MASK = R - 1; // 0xFF
    final int w = BITS / BITS_PER_BYTE;  // each int is 4 bytes

    int n = a.length;
    int[] aux = new int[n];

    for(int d = 0; d < w; d++)
    {
        // compute frequency counts
        int[] count = new int[R+1];

        for(int i = 0; i < n; i++)
        {           
            int c = (a[i] >> BITS_PER_BYTE*d) & MASK;
            count[c + 1]++;
        }

        // compute cumulates
        for(int r = 0; r < R; r++)
        {
            count[r+1] += count[r];
        }

        //for most significant byte, 0x80-0xFF comes before 0x00-0x7F
        if(d == (w - 1))
        {
            int shift1 = count[R] - count[R/2];
            int shift2 = count[R/2];

            for(int r = 0; r < R/2; r++)
            {
                count[r] += shift1;
            }

            for(int r = (R/2); r < R; r++)
            {
                count[r] -= shift2;
            }
        }

        // move data
        for(int i = 0; i < n; i++)
        {
            int c = (a[i] >> BITS_PER_BYTE*d) & MASK;
            aux[count[c]++] = a[i];
        }

        // copy back
        for(int i = 0; i < n; i++)
        {
            a[i] = aux[i];
        }
    }
}

Answer 1

嗯，就像你说的，没有可比性。最接近的操作是：

count[c + 1]++;

其中 c 是整数的一个字节。每个整数有 4 个字节，因此您正好执行 4*n 次。

基数排序数字比较

Radix sort digit compares

java

algorithm

radix-sort