数据结构与算法分析--学习笔记（4）

以下为基数排序的实现：

 

 

#include "stdio.h"
#include "stdlib.h"

struct Node{
       int Flag;
       int Array[ 10 ];
};

int Num[ 10 ] = { 310, 45, 22000, 18, 53, 29, 44, 730, 26, 44 };
int TmpNum[ 10 ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

void InitBucket( struct Node *Bucket ){
            int i;
            int m;
            for( i = 0; i < 10; i ++ ){
                 Bucket[ i ].Flag = 0;
                 for( m = 0; m < 10; m ++ ){
                      Bucket[ i ].Array[ m ] = 0;
                 }
            }
}

void SortBase( struct Node *Bucket, int *Num, int *TmpNum ){
       int i = 0;
       int t = 0;
       int s = 0;
       for( i = 0; i < 10; i ++ ){
              t = TmpNum[ i ];
              s = Bucket[ t ].Flag;
              Bucket[ t ].Array[ s ] = Num[ i ];
              Bucket[ t ].Flag = Bucket[ t ].Flag + 1;
       }
       s = 0;
       for( i = 0; i < 10; i ++ ){
            for( t = 0; t < 10; t ++ ){
                 if( Bucket[ i ].Array[ t ] != 0 ){
                     Num[ s ] = Bucket[ i ].Array[ t ];
                     s ++;
                 }
            }
       }
}

void Sort( struct Node *Bucket, int *Num, int *TmpNum ){
     int i = 0;
     int k = 1;
     int Sum = -1;
     while( Sum != 0 ){
            InitBucket( Bucket );
            for( i = 0; i < 10; i ++ )
                 TmpNum[ i ] = ( Num[ i ] / k ) % 10;
            Sum = 0;
            for( i = 0; i < 10; i ++ )
                 Sum = TmpNum[ i ] + Sum;
            k = k * 10;
            SortBase( Bucket, Num, TmpNum );
     }
}

main(){
       struct Node Bucket[ 10 ];
       int i = 0;
       Sort( Bucket, Num, TmpNum );
       for( i = 0; i < 10; i ++ )
       printf( "%d\n", Num [ i ] );
       getchar();
            
}