[C/C++ 演算法]-資料結構與演算法(文魁)：基數排序

 

線上執行結果：http://www.tutorialspoint.com/compile_c_online.php

 

 

/* =============== Program Description =============== */
/* 程式名稱 : 6_7.cpp				       */
/* 程式目的 : 基數排序				       */
/* 輸    入 : 排序前的整數陣列資料		       */
/* 輸    出 : 排序後的整數陣列資料		       */
/* =================================================== */
#define n 20
// 宣告標頭檔
#include "stdio.h"
// 宣告函式原型
// 利用傳址的方式把Array A傳進radix_sort函式中
void radix_sort(int *A);
// 利用傳址的方式把Array A傳進maxNumber函式中
int maxNumber(int *A);
// 利用傳值的方式把整數no傳進maxdigit函式中
int maxdigit(int no);
// 利用傳值的方式把整數no及整數kth傳進digitk函式中
int digitk(int no,int kth);
void main(void)
{
int i;
int A[n]={1,21,0,47,60,
15,84,65,77,88,
100,93,8,17,36,
5,24,63,72,20};
// 排序前的資料
printf(" Data before sorting \n");
for(i=0;i<n;i++)
printf("%d",A[i]);
printf("\n");
radix_sort(A);
// 排序後的資料
printf(" Data after sorting \n");
for(i=0;i<n;i++)
printf("%d",A[i]);
printf("\n");
getchar();
}
void radix_sort(int *A)
{
int i,j,k,index,no;
int maxno;
int digitno;
// 數字陣列資料暫��區的計數
int nocount[10]={0,0,0,0,0,0,0,0,0,0};
// 數字陣列資料的暫��區
int noarray[10][n];
// 取得陣列資料的最大值
maxno=maxNumber(A);
// 取得數字的最大位數，0代表1位數，1代表2位數... 
digitno=maxdigit(maxno);
//for (i=0;i<=digitno;i++)		
for (i=0;i<=2;i++)
{
for(j=0;j<=9;j++)
nocount[j]=0;
for(j=0;j<=n-1;j++)
{
// 取出資料的數字
no=digitk(A[j],i);
noarray[no][nocount[no]]=A[j];
nocount[no]=nocount[no]+1;
}
index = 0;
// 取出各數字陣列的資料回A陣列
for(j=0;j<=9;j++)
{
for(k=0;k<nocount[j];k++)
{
A[index]=noarray[j][k];
index++;
}
}
}
}
// 傳回陣列中最大的整數
int maxNumber(int *A)
{
int j,max=0;
for(j=0;j<n;j++)
if(A[j]>=max)
max=A[j];
return max;
}
// 傳回整數的位數，0代表1位數，1代表2位數... 
int maxdigit(int no)
{
int j;
for(j=0;;j++)
{
no = (int)(no/10);
if( no < 1 )
return j;
}
}
// 傳回第k位數字
int digitk(int no,int kth)
{
int i,j,m;
if (kth==0)
return no % 10;
else
{
for(j=0;j<kth;j++)
{
if(j==0)
m=10;
else
m=m*10;
}
i= ( (int)(no / m) )%10;
return i;
}
}