111101000跟111101011，重號的部分為111101000，至少會經歷5次不必要的遞迴，只要去除重號，就可以避免，但由於根除重號需要取出每一個數字逐一做&運算，因此至少需要多耗費一次尋找全部成員做計算的時間。(此部分請依數值的分布範圍自行做彈性調整)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct _atom_ {
unsigned int token;
unsigned int number;
struct _atom_ *next;
} atom;
typedef struct _OrderStack_ {
atom *head;
atom *end;
} OrderStack;
unsigned int one = 1;
unsigned int orderSize;
unsigned int *OrderList;
unsigned int orderID = 0;
unsigned int log_2_Largest(unsigned int number)
{
unsigned int length;
asm ("bsr %0,%0" : "=r" (length) : "r" (number));
return length;
}
unsigned int log_2_Least(unsigned int number)
{
unsigned int length;
asm ("bsf %0,%0" : "=r" (length) : "r" (number));
return length;
}
unsigned int getIndex(unsigned int number)
{
return log_2_Least(number);
}
void ExpSort(atom* atomListMenber_head, int maxLog2bit)
{
unsigned int BitSearchingIndex = 0;
OrderStack orderStack[maxLog2bit];
atom* nextMenber;
for(atom *atomListMenber = atomListMenber_head; atomListMenber != NULL; atomListMenber = nextMenber)
{
nextMenber = (*atomListMenber).next;
unsigned int stackIndex = log_2_Largest((*atomListMenber).token);
if((BitSearchingIndex | (one << stackIndex)) > BitSearchingIndex)
{
orderStack[stackIndex].head = atomListMenber;
orderStack[stackIndex].end = orderStack[stackIndex].head;
(*(orderStack[stackIndex].end)).next = NULL;
BitSearchingIndex |= (one << stackIndex);
}
else
{
(*(orderStack[stackIndex].end)).next = atomListMenber;
orderStack[stackIndex].end = atomListMenber;
(*(orderStack[stackIndex].end)).next = NULL;
}
}
if((BitSearchingIndex ^ one) < BitSearchingIndex)
{
for(atom *stackMenber = orderStack[0].head; stackMenber != NULL; stackMenber = (*stackMenber).next)
{
if((*stackMenber).token == 0)
{
*(OrderList + orderID) = (*stackMenber).number;
orderID++;
}
}
for(atom *stackMenber = orderStack[0].head; stackMenber != NULL; stackMenber = (*stackMenber).next)
{
if((*stackMenber).token == 1)
{
*(OrderList + orderID) = (*stackMenber).number;
orderID++;
}
}
BitSearchingIndex ^= one;//找到的位置擦除後才能繼續找下一個
}
while(BitSearchingIndex > 0)
{
unsigned int stackIndex = getIndex(BitSearchingIndex);
if(orderStack[stackIndex].head != orderStack[stackIndex].end)
{
unsigned int repeatPartMask;
if(stackIndex < 3)
{
repeatPartMask = one << stackIndex;
}
else
{
repeatPartMask = (*(orderStack[stackIndex].head)).token;
for(atom *stackMenber = orderStack[stackIndex].head; stackMenber != NULL; stackMenber = (*stackMenber).next)
{
repeatPartMask &= (*stackMenber).token;//取得重號特徵
}
}
for(atom *stackMenber = orderStack[stackIndex].head; stackMenber != NULL; stackMenber = (*stackMenber).next)
{
(*stackMenber).token ^= repeatPartMask;//擦除重號
}
ExpSort(orderStack[stackIndex].head, stackIndex - 1);
}
else
{
*(OrderList + orderID) = (*(orderStack[stackIndex].head)).number;
orderID++;
}
BitSearchingIndex ^= one << stackIndex;//找到的位置擦除後才能繼續找下一個
}
}
void expCountingSort(unsigned int numberList[], unsigned int size)
{
orderSize = size;
if(size == 0)
;
else if(size == 1)
{
;
}
else
{
unsigned int repeatPartMask = numberList[0];
for(int ID = 1; ID < size; ID++)
{
repeatPartMask &= numberList[ID];//取得重號特徵
}
atom* head;
head = (atom *) malloc(sizeof(atom));
(*head).token = numberList[0];
(*head).number = numberList[0];
(*head).next = NULL;
atom *end = head;
for(int ID = 1; ID < size; ID++)
{
(*end).next = (atom *) malloc(sizeof(atom));
end = (*end).next;
(*end).token = (numberList[ID] ^ repeatPartMask);//擦除重號
(*end).number = numberList[ID];
(*end).next = NULL;
}
ExpSort(head, 32);
}
}
int main()
{
unsigned int seed;
seed = (unsigned)time(NULL); // 取得時間序列
srand(seed);
unsigned int size = (rand() & 255) + 1;
unsigned int numberList[size];
for(int index = 0; index < size; index++)
{
numberList[index] = (rand() & 2147483647);
}
for(int index = 0; index < size; index++)
{
printf("%d,", numberList[index]);
}
printf("\n");
OrderList = (unsigned int *)numberList;
expCountingSort(numberList, size);
for(int index = 0; index < orderSize; index++)
{
printf("%d,", numberList[index]);
}
return 0;
}
LINE