Re: [問題] 排序法的問題
※ 引述《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
07/13 23:52, 2F
→
07/14 00:08, , 3F
07/14 00:08, 3F
※ 編輯: PkmX 來自: 114.25.210.26 (07/14 00:09)
討論串 (同標題文章)