溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶(hù)服務(wù)條款》

使用c語(yǔ)言怎么實(shí)現(xiàn)基數(shù)排序

發(fā)布時(shí)間:2021-04-08 16:52:06 來(lái)源:億速云 閱讀:203 作者:Leah 欄目:編程語(yǔ)言

使用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è)資訊頻道,感謝各位的閱讀!

向AI問(wèn)一下細(xì)節(jié)

免責(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)容。

AI