为什么我的Radix sort JAVA实现比Quick Sort慢？

Question

我正在尝试使用ByteBuffer.allocate()编写基数代码。

我了解到基数排序的时间复杂度是O(kn)，我写了这段代码来实现k=4。

我还编写了快速排序，并计算出我的基数排序比快速排序慢2到3倍。

是不是因为内存访问效率低？

这是我的基数排序代码。

private static int[] radixSort(int[] value)
{

    byte[][] valueByBytes = new byte[value.length][4];
    for (int i=0; i<value.length; i++) {
        valueByBytes[i] = ByteBuffer.allocate(4).putInt(value[i]).array();
    }

    for (int key = 3; key >=0; key--) {
        valueByBytes = countingSort(valueByBytes, key);
    }

    for (int i=0; i<value.length; i++) {
        value[i] = ByteBuffer.wrap(valueByBytes[i]).getInt();
    }
    return (value);
}

private static byte[][] countingSort(byte[][] valueByBytes, int key) {
    int[] countingArr = new int[256]; // 0 ~ 255
    byte[][] toReturnArr = new byte[valueByBytes.length][4];
    for (int i=0; i<256; i++) {
        countingArr[i] = 0;
    }

    int[] intArr = new int[valueByBytes.length];

    if (key > 0) {
        for (int j=0; j<valueByBytes.length; j++) {
            intArr[j] = (int) valueByBytes[j][key] >= 0 ? valueByBytes[j][key] : 256+valueByBytes[j][key];
        }
    }
    else {
        for (int j=0; j<valueByBytes.length; j++) {
            intArr[j] = (int) valueByBytes[j][key] + 128;
        }
    }

    for (int j=0; j<intArr.length; j++) {
        countingArr[intArr[j]]++;
    }

    for (int i=1; i<256; i++) {
        countingArr[i] = countingArr[i-1] + countingArr[i];
    }

    for (int j=intArr.length-1; j>=0; j--) {
        toReturnArr[countingArr[intArr[j]]-1] = valueByBytes[j];
        countingArr[intArr[j]]--;
    }

    return toReturnArr;
}

Answer 1

基数排序需要O(x_k_n)时间。其中K是位数。快速排序需要O(y_n_log n)，其中x> y，从较长的密钥中提取比特可能是一种昂贵的操作。这里使用的管理费用在您的情况下可能会带来麻烦。

你可以通过参考这个问题When should we use Radix sort?来获得更多的答案

Answer 2

使用ByteBuffer和所有的copy|convert操作会降低基数排序的速度。我测试了16777216个整数的排序，在我的系统上(Intel 3770K，Windows 7 Pro 64位，Netbeans 8.2)，问题的基数排序大约需要16.7秒，而下面显示的基数排序的实现大约需要0.55秒(大约快30倍)，而下面显示的快速排序的实现大约需要1.8秒。

package x;
import java.util.Random;

public class x {

    public static void RadixSort(int[] a)
    {
        int count = a.length;
        if(count < 2)
            return;
        int[] b = new int[count];           // allocate working array
        int [][] mIndex = new int[4][256];  // histograms | indexes
        int i,j,m,n,u;
        for(i = 0; i < count; i++){         // generate histograms
            u = a[i];
            mIndex[0][u&0xff]++;
            u >>= 8;
            mIndex[1][u&0xff]++;
            u >>= 8;
            mIndex[2][u&0xff]++;
            u >>= 8;
            mIndex[3][u+128]++;
        }
        for(j = 0; j < 4; j++){             // convert to indices
            m = 0;
            for(i = 0; i < 256; i++){
                n = mIndex[j][i];
                mIndex[j][i] = m;
                m += n;
            }       
        }
        for(i = 0; i < count; i++){         //  radix sort
            u = a[i];
            m = u&0xff;
            b[mIndex[0][m]++] = u;
        }
        for(i = 0; i < count; i++){
            u = b[i];
            m = (u>>8)&0xff;
            a[mIndex[1][m]++] = u;
        }
        for(i = 0; i < count; i++){
            u = a[i];
            m = (u>>16)&0xff;
            b[mIndex[2][m]++] = u;
        }
        for(i = 0; i < count; i++){
            u = b[i];
            m = (u>>24)+128;
            a[mIndex[3][m]++] = u;
        }
    }

    public static void main(String[] args) {
        int[] a = new int[16*1024*1024];
        Random r = new Random(0);
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        RadixSort(a);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }
}

    @SuppressWarnings("empty-statement")
    public static void qsort(int[] a, int lo, int hi)
    {
        if(lo >= hi)
            return;
        int  p = a[lo+(hi-lo)/2];
        int  i = lo-1;
        int  j = hi+1;
        int t;
        while(true){                // partition
            while(a[++i] < p);
            while(a[--j] > p);
            if(i >= j)
                break;
            t     = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        qsort(a, lo, j);
        qsort(a, j+1, hi);
    }