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

看板C_and_CPP作者 (Tangent)時間14年前 (2011/07/13 15:33), 編輯推噓0(000)
留言0則, 0人參與, 最新討論串2/3 (看更多)
※ 引述《heymei0421 (heymei)》之銘言: : 大家好.. : 小弟剛初學c++,遇到老師第一個HW題目之一,雖然老師給code了 : 很努力地看懂,很努力地和學長討論,但還是有幾個地方不了解.. : 題目: : 今天我給的數字型態有:signed,unsinged,char : 比如說給這三組: : 第一組: 12867 12876 13479 14778 12222 11447 : 第二組: -12345 47789 -78912 -77889 47564 : 第三組: big cat dog elephan apple banana : 輸入上面三組 要自動排序: : 根據助教的說明 他說明 利用radix排序法當外皮 counting排序法當骨頭 : 我實在搞不懂為什麼要這麼麻煩,因為counting排序法應該就可以做了.. : 而老師給的解答code,我有幾個地方和學長研究個老半天都無解.. : 麻煩熱心的大大幫忙解惑..有問題的地方有三個..Q.Q : 解惑的大大,小弟奉上1500p幣>"< : 老師的code如下: : #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? 因為sizeof是算byte數的 現在是以16進位為一組所以要乘以二 : 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; : 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]; //問題為什麼這邊要做累加? 做累加是因為數值愈高 就要愈後面 對於每次的radix 要由小到大 0 < 1 < 2 < 3 < 4 < 5 < 6.... 所以要做累加 : 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]; : } : for (int i=0;i<n;i++) a[i]=b[i]; : } : delete [] b; : } : //問題上述程式哪邊是做radix sort? 對映: for (int i=0;i<n;i++) { int k=a[i]>>4*d&0xF; if (d==digits-1&&numeric_limits<T>::is_signed) k=(k+8)%16; c[k]++; } 給個範例: [index]= 0 1 2 3 4 5 6 Array = 0x3579 0x3597 0x3245 0x3254 0x4235 0x4253 0x5379 第一次: 0x 3 5 7 9 -->c[9] 0x 3 5 9 7 -->c[7] 0x 3 2 4 5 -->c[5] 0x 3 2 5 4 -->c[4] 0x 4 2 3 5 -->c[5] 0x 4 2 5 3 -->c[3] 0x 5 3 7 9 -->c[9] [index] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 c 0 0 0 1 1 2 0 1 0 2 0 0 0 0 0 0 ===================add======================== c 0 0 0 1 2 4 4 5 5 7 7 7 7 7 7 7 在對應回來 [index]: 0 1 2 3 4 5 6 B : 0x4253 0x3254 0x3245 0x4235 0x3597 0x3579 0x5379 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.240.129.15 ※ 編輯: firejox 來自: 123.240.129.15 (07/13 23:44) ※ 編輯: firejox 來自: 123.240.129.15 (07/14 00:03)
文章代碼(AID): #1E7RgyMM (C_and_CPP)
討論串 (同標題文章)
本文引述了以下文章的的內容:
問題
1
9
完整討論串 (本文為第 2 之 3 篇):
問題
1
9
文章代碼(AID): #1E7RgyMM (C_and_CPP)