創作內容

0 GP

利用二進位數值的分布做數列排序(推廣版)

作者：藍貓│2019-01-04 22:51:01│巴幣：0│人氣：99

不同的地方在於:
1.以串列取代固定大小的陣列儲存待排數列，所以數字的分佈密度跟數量沒有限制。

2.對重號情況的數列有最佳表現，例如:
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;
}

喜歡 收藏 引用 留言 推上首頁 檢舉
引用網址：https://home.gamer.com.tw/TrackBack.php?sn=4250325
All rights reserved. 版權所有，保留一切權利

相關創作
DIGSTA『人中之龍 』模型發售總整理，以及SEGA STORE限定特典內容
【不定時日誌】檔案日服季復刻喔喔喔喔我還不抽爆啊啊啊啊啊啊啊啊!!!!
BTC 減半預測 二更
收齊整套笑鴗鳥一盎司銀幣
【yotoo】240418

留言共 0 篇留言

我要留言提醒：您尚未登入，請先登入再留言

喜歡★ertyk122 可決定是否刪除您的留言，請勿發表違反站規文字。

前一篇：非洲豬瘟特性... 後一篇：喜歡獸人動漫的理由...

追蹤私訊切換新版閱覽

作品資料夾

小說連載 (0)
└英雄聯盟小說（英雄聯盟系列） (19)
└［外傳］昏黃歲月（英雄聯盟系列） (1)
└阿宅與美女代打（英雄聯盟系列） (0)
└[寫實小說]＿糾心恥笑園 (0)
└[寫實小說]＿倒數末日 (0)
└[寫實小說]＿憂鬱天堂 (2)
└[寫實小說]＿網路殺人魔 (0)
└[寫實小說]＿錢魔 (0)
└[神幻小說]＿犬族的命運 (58)
└[神幻小說]＿捨不得你。妄想 (0)
└國中生小說 (3)

漫畫連載 (0)
└[搞笑四格]＿場外舉人 (0)
└[少年漫畫]＿台北大地震 (0)
└[少年漫畫]＿就是愛運動 (0)
└[少年漫畫]＿餵愛一口香 (0)
└[寫實漫畫]＿白狼 (0)
└[寫實漫畫]＿天刑三二三 (0)
└[寫實漫畫]＿橫血英雄 (0)
└[寫實漫畫]＿恐龍妹 (0)
└[神幻漫畫]＿剩水童子 (0)
└[神幻漫畫]＿永遠的父女 (0)
└[神幻漫畫]＿勇者我家人 (0)
└[其它]_音魂 (1)

劇本創作 (0)
└[寫實劇本]＿白狼 (1)
└[寫實劇本]＿天刑三二三 (0)
└[神幻劇本]＿繪魔 (0)
└[神幻劇本]＿魔曲 (0)

電腦理論 (6)
└程式設計相關理論 (14)
└高階程式語言理論 (6)
└實作程式 (15)
└程序之相關問題 (0)
└硬體管理與計算機結構 (3)

創作理論 (3)
└文學理論 (3)
└文學實作要領 (0)
└繪畫理論 (1)

生活日記 (241)
└自我提醒 (5)

文創作品 (2)
└散文與詩 (25)
└故事大綱 (1)
└繪圖 (57)
└processing文創應用 (0)
└勇造創作 (3)

數學領域相關證明 (0)

英雄聯盟豪洨文 (3)

辯論大會 (0)

未分類 (22)

dhreekingdon 給 幸運看見的你：
給你一顆紅心~讓你能保有一整天的好心情~祝你有個愉快的一天喲(<ゝω・)~❤看更多我要大聲說昨天22:55


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準，可能無法使用新的應用程式來呈現網站內容，在瀏覽器支援度及網站安全性的雙重考量下，為了讓巴友們有更好的使用體驗，巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特：
。Google Chrome（推薦）
。Mozilla Firefox
。Microsoft Edge（Windows10以上的作業系統版本才可使用）

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營，請將 gamer.com.tw 加入廣告阻擋工具的白名單中，謝謝 !【教學】