Re: [問題] 排序法的問題
※ 引述《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)
討論串 (同標題文章)