爲什麼我的排序程序太慢？ （基數/桶排序java）

Question

這是一個基數/桶排序混合，硬編碼爲9位數字。我的快速排序程序快兩倍，可以排序10米數字。我已經驗證了輸出是正確的，但速度很慢。

代碼：

public static void main(String[] args) { 
    Scanner in = new Scanner(System.in); 
    ArrayList<Integer> inputs = new ArrayList<>(); 
    while (in.hasNext()) { 
     inputs.add(in.nextInt()); 
    } 
    radixSort(inputs); 
    //System.out.print(toString(radixSort(inputs))); 
} 

public static ArrayList<Integer> radixSort(ArrayList<Integer> a) { 
    for (int i = 1; i <= 9; i++) { 
     a = bucketSort(a, i); 
    } 
    return a; 
} 

public static ArrayList<Integer> bucketSort(ArrayList<Integer> a, int index) { 
    // Creates buckets 
    ArrayList<ArrayList<Integer>> b = new ArrayList<ArrayList<Integer>>(); 
    for (int i = 0; i < 10; i++) { 
     b.add(new ArrayList<Integer>()); 
    } 
    // Sorts into buckets 
    for (int i = 0; i < a.size(); i++) { 
     b.get(key(a.get(i), index)).add(a.get(i)); 
    } 
    // Concatenates buckets 
    ArrayList<Integer> c = new ArrayList<>(); 
    for (int i = 0; i < b.size(); i++) { 
     c.addAll(b.get(i)); 
    } 
    return c; 
} 

// Takes an integer and index and returns digit at index 
public static int key(int num, int ind) { 
    int digit = num/(int)Math.pow(10, ind - 1); 
    digit = digit % 10; 
    return (int)digit; 
} 

public static String toString(ArrayList<Integer> a){ 
    StringBuilder s = new StringBuilder(); 
    for (int i = 0; i < a.size(); i++){ 
     s.append(String.format("%09d\n", a.get(i))); 
    } 
    return s.toString(); 
} 

Answer 1

爲緩慢的主要原因是附加在同一時間給每個桶陣列的一個整數，不必爲了以連接水桶，其中涉及動態擴展陣列再次追加。

最低有效位數第一個桶排序的計數變化會對與原始數組大小相同的第二個數組進行一次性分配。對於9位數的例子，它可以爲每個數字產生'0'，'1'，...'9'的次數，然後將這些計數轉換爲每個變量開頭的起始索引存儲桶，無需連接。對於9位數的例子，矩陣[9] [10]可以用於計數/指數，所以只有一個通過將被用於生成矩陣。

維基文章：進行排序的使用字節大小的 「數字」 32位無符號整數的數組

http://en.wikipedia.org/wiki/Counting_sort

例C++代碼，所以計數/索引的矩陣是[4] [256]。這個唯一的C++部分是std :: swap（），否則就是C代碼。

typedef unsigned int uint32_t; 

// a is input array, b is working array 
uint32_t * RadixSort(uint32_t * a, uint32_t *b, size_t count) 
{ 
size_t mIndex[4][256] = {0};   // count/index matrix 
size_t i,j,m,n; 
uint32_t u; 
    for(i = 0; i < count; i++){   // generate histograms 
     u = a[i]; 
     for(j = 0; j < 4; j++){ 
      mIndex[j][(size_t)(u & 0xff)]++; 
      u >>= 8; 
     }  
    } 
    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(j = 0; j < 4; j++){    // radix sort 
     for(i = 0; i < count; i++){  // sort by current lsb 
      u = a[i]; 
      m = (size_t)(u>>(j<<3))&0xff; 
      b[mIndex[j][m]++] = u; 
     } 
     std::swap(a, b);    // swap ptrs 
    } 
    return(a); 
}