[問題] 排序法的問題
大家好..
小弟剛初學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?
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]; //問題為什麼這邊要做累加?
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?
template<>
void radixsort<char*>(char** a,int n)
{
int* x=new int[n];
for (int i=0;i<n;i++) x[i]=strlen(a[i])*n+i;
radixsort(x,n);
for (int i=0;i<n;i++) x[i]%=n;
char** b=new char*[n];
for (int i=0;i<n;i++) b[i]=a[x[i]];
for (int i=0;i<n;i++) a[i]=b[i];
delete [] x;
const int digits=strlen(a[n-1]);
for (int d=digits-1;d>=0;d--) {
int c[256]={0};
int k;
for (k=n-1;k>=0;k--)
if (strlen(a[k])>d) c[a[k][d]]++; else break;
k++;
for (int i=1;i<256;i++) c[i]+=c[i-1];
for (int i=n-1;i>=k;i--) b[k+ --c[a[i][d]]]=a[i];
for (int i=n-1;i>=k;i--) a[i]=b[i];
}
delete [] b;
}
int main()
{
cout << "Test 1\n";
unsigned short a[]={0x3579,0x3597,0x3245,0x3254,0x4235,0x4253,0x5379,
0x3759,0x3795,0x3425,0x3524,0x4325,0x4523,0x5739,
0x3957,0x3975,0x3452,0x3542,0x4352,0x4532,0x5937};
radixsort(a,24);
for (int i=0;i<24;i++) cout << a[i] << ' '; cout << endl;
cout << "\nTest 2\n";
signed b[]={0xA345A345,0x23542354,0xA245A245,0x32543254,0xA235A235,
0xB435B435,0x24532453,0xB425B425,0x35243524,0xB325B325,
0xC543C543,0x25342534,0xC452C452,0x35423542,0xC352C352};
radixsort(b,24);
for (int i=0;i<24;i++) cout << b[i] << ' '; cout << endl;
cout << "\nTest 3\n";
char* c[27]={"boggy","snoot","cat","dog","doggy","garage","snooper",
"egg","cafe","dig","snoopy","cats","pluto","snooty",",
"zoo","smoke","bigger","snoop","bog","cab","garfield"};
radixsort(c,27);
for (int i=0;i<27;i++) cout << c[i] << ' '; cout << endl;
}
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.37.165.71
→
07/13 22:52, , 1F
07/13 22:52, 1F
→
07/13 23:03, , 2F
07/13 23:03, 2F
→
07/13 23:09, , 3F
07/13 23:09, 3F
→
07/13 23:10, , 4F
07/13 23:10, 4F
→
07/13 23:16, , 5F
07/13 23:16, 5F
→
07/13 23:16, , 6F
07/13 23:16, 6F
推
07/15 14:22, , 7F
07/15 14:22, 7F
→
07/15 22:19, , 8F
07/15 22:19, 8F
→
07/15 22:20, , 9F
07/15 22:20, 9F
討論串 (同標題文章)