基数排序

1.      基本思想

实现排序主要是通过关键字间的比较和移动记录这两种操作，而实现基数排序不需要进行记录关键字间的比较，它是一种利用多关键字排序的思想，即借助"分配"和"收集"两种操作对单逻辑关键字进行排序的方法。

基数排序的方法是：一个逻辑关键字可以看成由若干个关键字复合而成的，可把每个排序关键字看成是一个d元组：

例如，如果关键字是数值，且其值在0~99范围内，则可把每一个十进制数字看成是一个关键字，即可认为K由2个关键字（K0，K1）组成，其中K0是十位数，K1是个位数。排序时先按 的值从小到大将记录分配到r个盒子中，然后依次收集这些记录，再按 的值分配到r个盒子中，如此反复，直到对分配后收集起来的序列，便是完全排序的状态，其中r称为基数。这个过程是按LSD（最低位优先法）进行排序的，即从最低数位关键字起，按关键字的不同值对序列中记录"分配"和"收集"的。基数的选择和关键字的分解法因关键字的类型而异。

为了实现记录的"分配"和"收集"，需设立r个队列，排序前将队列设置为空，分配时，将记录插入到各自的队列中去，收集时将这些队列中记录排在一起。

一般采用静态链表作为记录序列的存储结构，并且不另外设置各链队列的结点空间，而是利用静态链表中的结点作为链队列中的结点，这样只需修改指针即可完?quot;分配"和"收集"任务。时间复杂度为O（d（n+rd））



在基数排序算法中，没有进行关键字的比较和记录的移动，而只是顺链扫描链表和进行指针赋值，所以，排序的时间主要耗费在修改指针上。对于n个记录（假设每个记录含d个关键字，每个关键字的取值范围为rd个值）进行一趟分配的时间复杂度为O（n），进行一趟收集的时间复杂度为O（rd），整个排序过程需要进行d趟分配和收集操作。因此，链式基数排序总的时间复杂度为O（d（n+rd））。

当n较小，d较大时，基数排序并不合适。只有当n较大，d较小时，特别是记录的信息量较大时，基数排序最为有效。基数排序中所需辅助空间为2rd个队列指针，另外每个记录中都增加了一个指针域。

2.程序

#include

#include



// constant size must be defined as the array size for bucketSort to work

const int SIZE = 12;



void bucketSort( int [] );

void distributeElements( int [], int [][ SIZE ], int );

void collectElements( int [], int [][ SIZE ] );

int numberOfDigits( int [], int );

void zeroBucket( int [][ SIZE ] );



int main()

{

int array[ SIZE ] = { 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21 };



cout << "Array elements in original order:\n";



for ( int i = 0; i < SIZE; ++i )

cout << setw( 3 ) << array[ i ];



cout << '\n';

bucketSort( array );



cout << "\nArray elements in sorted order:\n";



for ( int j = 0; j < SIZE; ++j )

cout << setw( 3 ) << array[ j ];



cout << endl;

return 0;

}



// Perform the bucket sort algorithm

void bucketSort( int a[] )

{

int totalDigits, bucket[ 10 ][ SIZE ] = { 0 };



totalDigits = numberOfDigits( a, SIZE );



for ( int i = 1; i <= totalDigits; ++i ) {

distributeElements( a, bucket, i );

collectElements( a, bucket );



if ( i != totalDigits )

zeroBucket( bucket ); // set all bucket contents to zero

}

}



// Determine the number of digits in the largest number

int numberOfDigits( int b[], int arraySize )

{

int largest = b[ 0 ], digits = 0;



for ( int i = 1; i < arraySize; ++i )

if ( b[ i ] > largest )

largest = b[ i ];



while ( largest != 0 ) {

++digits;

largest /= 10;

}



return digits;

}



// Distribute elements into buckets based on specified digit

void distributeElements( int a[], int buckets[][ SIZE ], int digit )

{

int divisor = 10, bucketNumber, elementNumber;



for ( int i = 1; i < digit; ++i ) // determine the divisor

divisor *= 10; // used to get specific digit



for ( int k = 0; k < SIZE; ++k ) {

// bucketNumber example for hundreds digit:

// (1234 % 1000 - 1234 % 100) / 100 --> 2

bucketNumber = ( a[ k ] % divisor - a[ k ] %

( divisor / 10 ) ) / ( divisor / 10 );



// retrieve value in buckets[bucketNumber][0] to determine

// which element of the row to store a[i] in.

elementNumber = ++buckets[ bucketNumber ][ 0 ];

buckets[ bucketNumber ][ elementNumber ] = a[ k ];

}

}



// Return elements to original array

void collectElements( int a[], int buckets[][ SIZE ])

{

int subscript = 0;



for ( int i = 0; i < 10; ++i )

for ( int j = 1; j <= buckets[ i ][ 0 ]; ++j )

a[ subscript++ ] = buckets[ i ][ j ];

}



// Set all buckets to zero

void zeroBucket( int buckets[][ SIZE ] )

{

for ( int i = 0; i < 10; ++i )

for ( int j = 0; j < SIZE; ++j )

buckets[ i ][ j ] = 0;

}