基數排序工作

Question

我想知道下面的基數排序程序的邏輯。

#include <stdio.h> 
#include <limits.h> 
#include <stdlib.h> 

typedef unsigned uint; 
#define swap(a, b) { tmp = a; a = b; b = tmp; } 
#define each(i, x) for (i = 0; i < x; i++) 

/* sort unsigned ints */ 
static void rad_sort_u(uint *from, uint *to, uint bit) 
{ 
    if (!bit || to < from + 1) return; 

uint *ll = from, *rr = to - 1, tmp; 
while (1) { 
    /* find left most with bit, and right most without bit, swap */ 
    while (ll < rr && !(*ll & bit)) ll++; 
    while (ll < rr && (*rr & bit)) rr--; 
    if (ll >= rr) break; 
    swap(*ll, *rr); 
} 

if (!(bit & *ll) && ll < to) ll++; 
bit >>= 1; 

rad_sort_u(from, ll, bit); 
rad_sort_u(ll, to, bit); 
} 

/* sort signed ints: flip highest bit, sort as unsigned, flip back */ 
static void radix_sort(int *a, const size_t len) 
{ 
size_t i; 
uint *x = (uint*) a; 

each(i, len) x[i] ^= INT_MIN; 
rad_sort_u(x, x + len, INT_MIN); 
each(i, len) x[i] ^= INT_MIN; 
} 

static inline void radix_sort_unsigned(uint *a, const size_t len) 
{ 
rad_sort_u(a, a + len, (uint)INT_MIN); 
} 

int main(void) 
{ 
int len = 16, x[16], i; 
size_t len = 16, i; 
each(i, len) x[i] = rand() % 512 - 256; 

radix_sort(x, len); 

each(i, len) printf("%d%c", x[i], i + 1 < len ? ' ' : '\n'); 

return 0; 
} 

我堅持，因爲我不太明白的，而（1）循環..

到目前爲止，我已經知道的是：

INT_MIN=-2147483648 

這是相同的價值在rad_short_u()

我已經調試的程序，由於rand() % 512-256bit，一些-ve值也產生，

第一次通過時，它將所有的-ve值交換到一側（從開始）和+ ve之後 從下一個通道它左移到1位，所以位值從1073741824變爲1073741824，直到它變爲1數組保持不變。

請幫我理解程序邏輯。

Answer 1

要了解這個程序，你需要了解兩個快速排序和最顯著位基數排序。

喜歡快速排序，它分隔所述陣列成零件，然後遞歸排序部件。它首先根據最高有效位的值進行分區。然後它在兩邊都會遞歸。但是這一次，對於每一半，它基於第二重要位進行分區。然後重新劃分，併爲每個1/4，其劃分的13類最顯著有點...

注意的是，雖然我說的「1/2」，「1/4」，等等，它通常不會將數組精確地分爲1/2,1/4等。每個分區的大小將取決於數組中的數字分佈。對於正常的快速排序，每個分區的大小取決於選擇爲「樞軸」的元素，但對於這個「基數快速排序」不是這樣 - 「樞軸」的順序是固定的。

還要注意，不像一個正常的快速排序，它可以去二次，併成爲某些輸入速度很慢，這種「快速排序」保證在固定的遍數來完成。實際上，無論輸入如何，所需通過次數都是一個常數。 （這是基數排序的典型屬性 - 性能往往對輸入不敏感）。

另一個有趣的屬性：正常的快速排序會將數組分成3個部分 - 那些小於，等於和大於樞。但是這個「快速排序」總是在每次通過時將其輸入精確地分爲2個部分 - 那些在測試位置具有0位的數據，以及具有1位的數據。

我覺得這個算法的名稱實際上是「二進制快速排序」。

Answer 2

你while(1)循環操作逐位的無符號整數。對於每一位，它從列表的頂部和底部開始，找到第一對整數，其中位設置在底部而不是頂部，並交換它們。這糾正了該位的這些值的排序。

它繼續這樣做直到頂部/底部相遇。最後，每次通過while(1)循環時，都會導致列表中的所有數字都在該列表底部未被設置，並且所有具有該位的數字都被設置在列表頂部。

然後按順序對列表進行排序，從MSB開始，然後是第二個MSB，...，最後是LSB。值INT_MIN對帶符號整數爲負，但對應於二進制補碼中的MSB。

x[i] ^= INT_MIN行允許基數排序正確處理負數。帶符號的整數以二進制補碼形式存儲。這實際上意味着負數具有MSB設置。

如果你天真地將一個基數類型應用於帶符號整數，最終的結果是排序的正數低於負數。

x[i] ^= INT_MIN翻轉MSB，它解決了這個問題。第二個x[i] ^= INT_MIN翻轉回來。