Re: [問題] 排序法的問題

看板C_and_CPP作者 (PkmX)時間14年前 (2011/07/13 15:49), 編輯推噓0(003)
留言3則, 3人參與, 最新討論串3/3 (看更多)
※ 引述《heymei0421 (heymei)》之銘言: : #include <iostream> : #include <limits> : #include <cstring> : using namespace std; : template<typename T> : void radixsort(T* a,int n) : { : T* b=new T[n]; : const int digits=sizeof(T)*2; //問題:為什麼這裡要乘2? 若一個整數有n個bytes,一共有n*8個bits,(假設1 byte=8 bits的話) 這裡是以一個nibble (0x0~0xF)作為radix,所以n*8個bits一共有n*8/4=n*2個nibbles : for (int d=0;d<digits;d++) { : int c[16]={0}; : for (int i=0;i<n;i++) { : int k=a[i]>>4*d&0xF; 這邊就是radix sort所在之處,k是代表a[i]的第d+1個least significant nibble, 例如a[i]=0x12345678,我要取第三個nibble (d=2),a[i] >> 4*2 = 0x00123456, 然後讓0x00123456和0xF做bitwise and就會得到0x00000006,剛好是第三個nibble, 最外層的loop剛好把所有的nibbles從最低位到最高位分別排序 : if (d==digits-1&&numeric_limits<T>::is_signed) k=(k+8)%16; : c[k]++; : } : for (int i=1;i<16;i++) c[i]+=c[i-1]; //問題為什麼這邊要做累加? 這邊要先了解counting sort的原理: 假設我要sort一個list a:(2 5 3 0 2 3 0 3),其中數字範圍為0~5,排序好的結果為b: b 0 1 2 3 4 5 6 7 0 0 2 2 3 3 3 5 ^ ^ ^ ^ 注意^標起來的地方,那是代表某個數字出現的最大的index, 如果我能算出每個數字最大出現的index是多少,我就可以很有效綠的填滿b, 首先算出每一個數字出現的次數: n 0 1 2 3 4 5 c 2 0 2 3 0 1 接下來算出比該數字小或相等的數字的個數(累加就是這一步): n 0 1 2 3 4 5 c 2 2 4 7 7 8 這時候,我就知道遇到0~5的數字的時候,它最大只能填在第幾個位置 : for (int i=n-1;i>=0;i--) { : int k=a[i]>>4*d&0xF; : if (d==digits-1&&numeric_limits<T>::is_signed) k=(k+8)%16; : b[--c[k]]=a[i]; : } 這邊就是在做填位置的動作,繼續以上面的list為例,從後往前看: 第一個遇到的數字是k = 3,查表後得到c[3] = 7,也就是3最大只能出現在第7個位置, 這時候我就可以把3填在b[6]這個位置(注意陣列的第一個為0,所以要減一), 而下一個3應該最大只能出在第6個位置,因為第7個已經被填了,所以把c[3]減一, (這裡code的b[--c[k]]已經把兩個減一合併在一起了) 接下來遇到k = 0,查表得知c[0] = 2,就把0填在b[1],然後c[0]減一, 接下來又遇到k = 3,這時候c[3]已經是6了,依照前面的作法,讓b[5] = 3, 以此類推,全部做完以後,b就是排序好的list了, 如果還是不懂的話,拿筆自己排一次就會懂了 : for (int i=0;i<n;i++) a[i]=b[i]; 這裡只是把結果b複製回a而已 : } : delete [] b; : } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.25.210.26

07/13 23:49, , 1F
囧 被搶先了
07/13 23:49, 1F

07/13 23:52, , 2F
兩位大大小弟都奉上1500 ^_^
07/13 23:52, 2F

07/14 00:08, , 3F
寫的真詳細m(_ _)m
07/14 00:08, 3F
※ 編輯: PkmX 來自: 114.25.210.26 (07/14 00:09)
文章代碼(AID): #1E7RvlEn (C_and_CPP)
討論串 (同標題文章)
本文引述了以下文章的的內容:
問題
1
9
完整討論串 (本文為第 3 之 3 篇):
問題
1
9
文章代碼(AID): #1E7RvlEn (C_and_CPP)