快捷導(dǎo)航

c語言實(shí)現(xiàn)基數(shù)排序解析及代碼示例

更新時(shí)間：2017年12月18日 11:20:03 作者：GejinZ

這篇文章主要介紹了c語言實(shí)現(xiàn)基數(shù)排序解析及代碼示例，具有一定借鑒價(jià)值，需要的朋友可以參考下。

1.

基數(shù)排序（radixsort）屬于“分配式排序”（distributionsort），又稱“桶子法”（bucketsort）或binsort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用。

2.基數(shù)排序的實(shí)現(xiàn)方法分為兩種：

最高位優(yōu)先(MostSignificantDigitfirst)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對各組按k2排序分成子組，之后，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對各子組排序后。再將各組連接起來，便得到一個(gè)有序序列。

最低位優(yōu)先(LeastSignificantDigitfirst)法，簡稱LSD法：先從kd開始排序，再對kd-1進(jìn)行排序，依次重復(fù)，直到對k1排序后便得到一個(gè)有序序列。

3.LSD基數(shù)排序的原理及代碼實(shí)現(xiàn)如下：

第一步

假設(shè)原來有一串?dāng)?shù)值如下所示：

73,22,93,43,55,14,28,65,39,81

首先根據(jù)個(gè)位數(shù)的數(shù)值，在走訪數(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

第二步

接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：

81,22,73,93,43,14,55,65,28,39

接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配：

0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

第三步

接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：

14,22,28,39,43,55,65,73,81,93

這時(shí)候整個(gè)數(shù)列已經(jīng)排序完畢；如果排序的對象有三位數(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; 
}

總結(jié)

以上就是本文關(guān)于c語言實(shí)現(xiàn)基數(shù)排序解析及代碼示例的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！

您可能感興趣的文章: