基本思想
實現(xiàn)排序主要是通過關(guān)鍵字間的比較和移動記錄這兩種操作，而實現(xiàn)基數(shù)排序不需要進行記錄關(guān)鍵字間的比較，它是一種利用多關(guān)鍵字排序的思想，即借助"分配"和"收集"兩種操作對單邏輯關(guān)鍵字進行排序的方法。
基數(shù)排序的方法是：一個邏輯關(guān)鍵字可以看成由若干個關(guān)鍵字復(fù)合而成的，可把每個排序關(guān)鍵字看成是一個d元組：
例如，如果關(guān)鍵字是數(shù)值，且其值在0~99范圍內(nèi)，則可把每一個十進制數(shù)字看成是一個關(guān)鍵字，即可認為K由2個關(guān)鍵字（K0，K1）組成，其中K0是十位數(shù)，K1是個位數(shù)。排序時先按 的值從小到大將記錄分配到r個盒子中，然后依次收集這些記錄，考試大提示:再按 的值分配到r個盒子中，如此反復(fù)，直到對分配后收集起來的序列，便是完全排序的狀態(tài)，其中r稱為基數(shù)。這個過程是按LSD（最低位優(yōu)先法）進行排序的，即從最低數(shù)位關(guān)鍵字起，按關(guān)鍵字的不同值對序列中記錄" 分配"和"收集"的?；鶖?shù)的選擇和關(guān)鍵字的分解法因關(guān)鍵字的類型而異。
為了實現(xiàn)記錄的"分配"和"收集"，需設(shè)立r個隊列，排序前將隊列設(shè)置為空，分配時，將記錄插入到各自的隊列中去，收集時將這些隊列中記錄排在一起。
一般采用靜態(tài)鏈表作為記錄序列的存儲結(jié)構(gòu)，并且不另外設(shè)置各鏈隊列的結(jié)點空間，而是利用靜態(tài)鏈表中的結(jié)點作為鏈隊列中的結(jié)點，這樣只需修改指針即可完?quot;分配"和"收集"任務(wù)。時間復(fù)雜度為O（d（n+rd））
在基數(shù)排序算法中，沒有進行關(guān)鍵字的比較和記錄的移動，Examda提示:而只是順鏈掃描鏈表和進行指針賦值，所以，排序的時間主要耗費在修改指針上。對于n個記錄（假設(shè)每個記錄含d個關(guān)鍵字，每個關(guān)鍵字的取值范圍為rd個值）進行一趟分配的時間復(fù)雜度為O（n），進行一趟收集的時間復(fù)雜度為O（rd），整個排序過程需要進行 d趟分配和收集操作。因此，鏈?zhǔn)交鶖?shù)排序總的時間復(fù)雜度為O（d（n+rd））。
當(dāng)n較小，d較大時，基數(shù)排序并不合適。只有當(dāng)n較大，d較小時，特別是記錄的信息量較大時，基數(shù)排序最為有效?；鶖?shù)排序中所需輔助空間為2rd個隊列指針，另外每個記錄中都增加了一個指針域。
#include
#include
using namespace std;
// 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;
system("pause");
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;
}
實現(xiàn)排序主要是通過關(guān)鍵字間的比較和移動記錄這兩種操作，而實現(xiàn)基數(shù)排序不需要進行記錄關(guān)鍵字間的比較，它是一種利用多關(guān)鍵字排序的思想，即借助"分配"和"收集"兩種操作對單邏輯關(guān)鍵字進行排序的方法。
基數(shù)排序的方法是：一個邏輯關(guān)鍵字可以看成由若干個關(guān)鍵字復(fù)合而成的，可把每個排序關(guān)鍵字看成是一個d元組：
例如，如果關(guān)鍵字是數(shù)值，且其值在0~99范圍內(nèi)，則可把每一個十進制數(shù)字看成是一個關(guān)鍵字，即可認為K由2個關(guān)鍵字（K0，K1）組成，其中K0是十位數(shù)，K1是個位數(shù)。排序時先按 的值從小到大將記錄分配到r個盒子中，然后依次收集這些記錄，考試大提示:再按 的值分配到r個盒子中，如此反復(fù)，直到對分配后收集起來的序列，便是完全排序的狀態(tài)，其中r稱為基數(shù)。這個過程是按LSD（最低位優(yōu)先法）進行排序的，即從最低數(shù)位關(guān)鍵字起，按關(guān)鍵字的不同值對序列中記錄" 分配"和"收集"的?；鶖?shù)的選擇和關(guān)鍵字的分解法因關(guān)鍵字的類型而異。
為了實現(xiàn)記錄的"分配"和"收集"，需設(shè)立r個隊列，排序前將隊列設(shè)置為空，分配時，將記錄插入到各自的隊列中去，收集時將這些隊列中記錄排在一起。
一般采用靜態(tài)鏈表作為記錄序列的存儲結(jié)構(gòu)，并且不另外設(shè)置各鏈隊列的結(jié)點空間，而是利用靜態(tài)鏈表中的結(jié)點作為鏈隊列中的結(jié)點，這樣只需修改指針即可完?quot;分配"和"收集"任務(wù)。時間復(fù)雜度為O（d（n+rd））
在基數(shù)排序算法中，沒有進行關(guān)鍵字的比較和記錄的移動，Examda提示:而只是順鏈掃描鏈表和進行指針賦值，所以，排序的時間主要耗費在修改指針上。對于n個記錄（假設(shè)每個記錄含d個關(guān)鍵字，每個關(guān)鍵字的取值范圍為rd個值）進行一趟分配的時間復(fù)雜度為O（n），進行一趟收集的時間復(fù)雜度為O（rd），整個排序過程需要進行 d趟分配和收集操作。因此，鏈?zhǔn)交鶖?shù)排序總的時間復(fù)雜度為O（d（n+rd））。
當(dāng)n較小，d較大時，基數(shù)排序并不合適。只有當(dāng)n較大，d較小時，特別是記錄的信息量較大時，基數(shù)排序最為有效?；鶖?shù)排序中所需輔助空間為2rd個隊列指針，另外每個記錄中都增加了一個指針域。
#include
#include
using namespace std;
// 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;
system("pause");
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;
}