快速排序的字節數組

Question

我有一個小問題，找不到滿意的解決方案。 有一個字節數組，我需要這些字節按高7位排序，而 保留低位的順序。

所以最初它看起來是這樣的：

// sort buf[N] to tmp[N] 
uint offs[128+1]; uint c,i,s; 
for(i=0; i<128; i++) offs[i]=0; 
for(i=0; i<l; i++) offs[buf[i]>>1]++; 
for(i=0,s=0; i<128; i++) c=offs[i], offs[i]=s, s+=c; offs[i]=s; 

byte* tmp = new byte[N]; 
for(i=0; i<N; i++) c=buf[i], tmp[offs[c>>1]++]=c; // sort 

但這些塊是足夠大（目前8M），我想用多線程， 和每個線程的額外8M是明顯的。

所以我試圖用一些簡單的基數排序：

void radix(byte* buf, uint h, uint l, uint mask) { 
    uint p = (h+l)>>1, q = h; 
    uint i = offs[h], j = offs[l]-1; h = offs[p]; 
    if((i<h) && (j>=h)) { 
    byte c = buf[i], d = buf[j]; 
    while((i<h) && (j>=h)) { 
     while((c&mask)==0) c = buf[++i]; // find value with bit 1 
     while((d&mask)!=0) d = buf[--j]; // find value with bit 0 
     buf[i]=d; buf[j]=c; // swap 1-0 -> 0-1 
     c = buf[++i]; d = buf[--j]; 
    } 
    if(mask>=4) { 
     radix(buf, q,p, mask>>1); 
     radix(buf, p,l, mask>>1); 
    } 
    } 
} 

但它改變了這些低位的順序，它變得不可用。

其實一些簡單的方法，像bubblesort，只是做我想要的，但它們慢得多，速度也是一個問題。

所以目前我排序經由臨時緩衝區更小的塊，然後使用 索引表來訪問，以便部分地排序的塊：

struct tmpsort { 

    enum{ blocksize = (1<<16)-1 }; 

    unsigned short ofs[(max_quants+blocksize-1)/blocksize][probN]; 

    tmpsort(byte* buf, uint f_len) { 
    uint i,j,k; 
    uint freq[2*probN]; // prob freqs 
    byte tmp[blocksize+1]; 

    for(k=0,j=0; k<f_len; k+=blocksize,j++) { 
     uint l = Min(k+blocksize,f_len)-k; 
     byte* p = &buf[k]; 

     // compute offsets of sorted chunks 
     for(i=0; i<2*probN; i++) freq[i]=0; 
     for(i=0; i<l; i++) freq[p[i]]++; 
     for(i=0; i<probN; i++) freq[i+1]=freq[2*i+0]+freq[2*i+1]; // 1=0+1, 2=2+3, 3=4+5 
     freq[0] = 0; 
     for(i=0; i<probN; i++) freq[i+1]+=freq[i]; 
     for(i=0; i<probN; i++) ofs[j][i]=freq[i+1]; 

     // sort the block via tmp 
     for(i=0; i<l; i++) { byte c=p[i]; tmp[freq[c>>1]++]=c; } 
     for(i=0; i<l; i++) p[i]=tmp[i]; 
    } 
    } 

}; 

[...] 

tmpsort ts(buf, f_len); 
for(i=0; i<probN; i++) { 
    for(k=0,j=0; k<f_len; k+=ts.blocksize,j++) { 
    uint x = i>0 ? ts.ofs[j][i-1] : 0; 
    for(; x<ts.ofs[j][i]; x++) putc(buf[k+x],g); 
    } 
} 

但是TMP []和OFS []陣列使用太多堆棧空間，它的 不是一個完整的排序，所以我一直想知道是否有一些整潔的解決方案。

數據和我實現的一個樣本在這裏可供選擇： http://nishi.dreamhosters.com/u/tmpsort_v0.rar

Answer 1

有了額外的64kB，你可以（如你所注意到的）以壓縮的形式存儲一個512kbit的塊（減去一些固定數量的索引數據）（只存儲每個鍵的最低位）。他們到他們壓縮排序的形式，壓縮他們，當你走在整個數組的開始。

現在將壓縮表單合併成一個大的壓縮表單（釋放7M後很容易）。然後解壓回到排序後的數組。

這是O（N），雖然常數看起來相當大，但涉及一些非平凡位操作的3遍。

Answer 2

爲什麼不使用任何標準就地，穩定sorting algorithm，例如Insertion Sort，並實現適當的比較器功能？

Answer 3

可以將quicksort作爲穩定的排序來實現。就big-O而言，它並不比插入排序更好，但實際上它會更好地執行批次。如果您對大小爲6或8的樹葉進行硬編碼排序網絡，我認爲這是您將獲得穩定的就地排序的最佳性能。

其實......據說有一種就地穩定的合併排序。就理想的理論特徵而言，它是所有在同一時間的原地排列，真正的穩定的聖盃。但我懷疑這是一個巨大的痛苦實施，並有相當大的恆定條件去與那個大O。

Answer 4

這可以用在超過O一點相對簡單的代碼使用一個版本的基數排序的執行在各7個重要比特的一個穩定的排序，從至少顯著到最顯著（N log n）的時間來完成。這種技術相對於穩定的就地合併排序的優點是，如果你自己編寫代碼，代碼就簡單得多。

下面是由一個規定的位來執行就地穩定排序的功能。這裏，遞歸編寫使用O（LG N）的堆棧空間的簡單（該堆棧空間的使用可以，如果你想使用一個for循環來組織分而治之的辦法消除）：

// sort array x from i to j by bit b 
sort(x, i, j, b) { 
    if (i >= j - 1) return; 
    mid = (i + j)/2; 
    sort(x, i, mid, b); 
    sort(x, mid, j, b); 
    first1 = -1; 
    last0 = -1; 
    for (k = i; k < j; k++) { 
    if (first1 < 0 && isSet(x[k], b)) first1 = k; 
    if (!isSet(x[k], b)) last0 = k; 
    } 
    if (last0 < first1) return; 

    // the sequence of bit b generally looks something like 0000011100000111111 
    // so we reverse from the first 1 to the last 0 
    reverse(x, first1, last0afterfirst1); 
    newlast0 = first1; 
    while (!isSet(x[++newlast0], b)); 
    newlast0--; 

    // the elements in the range first1..last0 are in the wrong order, so reverse 
    reverse(x, first1, newlast0); 
    reverse(x, newlast0 + 1, last0); 
} 

功能isSet測試是否設置了一位，reverse執行就地陣列反轉。上述排序子程序被調用的每個位（如在基數排序）如下：

sort(x) { 
    for (b = 1; b < 8; b++) { 
    sort(x, 0, n, b); 
    } 
} 

總運行時間爲「O（7 * N log n）的」。如果該算法得到推廣，則額外因子7可能是可變的。