您好,登錄后才能下訂單哦!
使用c語(yǔ)言怎么實(shí)現(xiàn)基數(shù)排序?相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策,為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法,通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。
1.基數(shù)排序(radixsort)屬于“分配式排序”(distributionsort),又稱(chēng)“桶子法”(bucketsort)或binsort,顧名思義,它是透過(guò)鍵值的部份資訊,將要排序的元素分配至某些“桶”中,藉以達(dá)到排序的作用。
2.基數(shù)排序的實(shí)現(xiàn)方法分為兩種:
最高位優(yōu)先(MostSignificantDigitfirst)法,簡(jiǎn)稱(chēng)MSD法:先按k1排序分組,同一組中記錄,關(guān)鍵碼k1相等,再對(duì)各組按k2排序分成子組,之后,對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組,直到按最次位關(guān)鍵碼kd對(duì)各子組排序后。再將各組連接起來(lái),便得到一個(gè)有序序列。
最低位優(yōu)先(LeastSignificantDigitfirst)法,簡(jiǎn)稱(chēng)LSD法:先從kd開(kāi)始排序,再對(duì)kd-1進(jìn)行排序,依次重復(fù),直到對(duì)k1排序后便得到一個(gè)有序序列。
3.LSD基數(shù)排序的原理及代碼實(shí)現(xiàn)如下:
第一步
假設(shè)原來(lái)有一串?dāng)?shù)值如下所示:
73,22,93,43,55,14,28,65,39,81
首先根據(jù)個(gè)位數(shù)的數(shù)值,在走訪(fǎng)數(shù)值時(shí)將它們分配至編號(hào)0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
第二步
接下來(lái)將這些桶子中的數(shù)值重新串接起來(lái),成為以下的數(shù)列:
81,22,73,93,43,14,55,65,28,39
接著再進(jìn)行一次分配,這次是根據(jù)十位數(shù)來(lái)分配:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
第三步
接下來(lái)將這些桶子中的數(shù)值重新串接起來(lái),成為以下的數(shù)列:
14,22,28,39,43,55,65,73,81,93
這時(shí)候整個(gè)數(shù)列已經(jīng)排序完畢;如果排序的對(duì)象有三位數(shù)以上,則持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int getDigitNum(int x){ if(x == 0) return 1; int res = 0; while(x){ res ++; x /= 10; } return res; } void RadixSort(int data[], int n){ //find the Maximum and its digit number int Max = data[0]; for(int i = 1; i < n; i++){ if(Max < data[i]) Max = data[i]; } int maxNum = getDigitNum(Max); //maxNum times radix sort int divisor = 1; for(int k = 0; k < maxNum; k++){ vector<int> g[10];//g[i]中包含了"末位"數(shù)字是i的data[]數(shù)組中的元素 for(int i = 0; i < 10; i++) g[i].clear(); for(int i = 0; i < n; i++){ int tmp = data[i] / divisor % 10; g[tmp].push_back(data[i]); } int cnt = 0; for(int i = 0; i < 10; i++){ for(int j = 0; j < g[i].size(); j++){ data[cnt++] = g[i][j]; } } divisor *= 10; } } int main(){ int Array[10] = {73,22,93,43,55,14,28,65,39,81}; RadixSort(Array, 10); for(int i = 0; i < 10; i++){ printf("%d ", Array[i]); } printf("\n"); return 0; }
看完上述內(nèi)容,你們掌握使用c語(yǔ)言怎么實(shí)現(xiàn)基數(shù)排序的方法了嗎?如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容,歡迎關(guān)注億速云行業(yè)資訊頻道,感謝各位的閱讀!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。