前言
当序列中元素范围比較大时，就不适合使用。针对这样的情况。就有了基数排序(Radix Sort)，这是一种按位排序。它仍然是以计数排序为基础。
基数排序
基数排序的基数：十进制数的基数自然是10，二进制的基数自然是2。通常有两种按位排序策略：1.高位优先法(most significant digit first,MSD)：简单讲就是从高位排起。2.低位优先法(least significant digit first,LSD)：它与高位优先相反，从低位排起。从排序效果上看，高位优先比較直观，但却涉及到递归的过程，故最经常使用的还是低位优先法。
说它以计数排序为基础，理由例如以下。以最常见的十进制数为例：
细致理解上图，高位优先的过程你也一定能够猜測出来。
以下给出低位优先下的代码。
代码
#include#include using namespace std;//获取最大位数int get_max_digit(int array[], int n){ int digit, max; digit = 0; max = array[0]; for (int i = 1; i < n; i++) { if (array[i] > max) max = array[i]; } while (max) { digit++; max /= 10; } return digit;}//基数排序void RadixSort(int array[], int n){ //创建暂时数组 int *temp = new int[n]; //位数：决定了排序趟数 int digit = get_max_digit(array, n); //计数数组 int count[10]; //排序 int r, i, d; for (r = 1; r <= digit; r++) { //重置计数数组 memset(count, 0, 10 * sizeof(int)); //把数据存储到暂时数组 memcpy(temp, array, n*sizeof(int)); d = i = 1; while (i < r) { i++; d *= 10; } for (i = 0; i < n; i++) count[(array[i] / d) % 10]++; for (i = 1; i < 10; i++) count[i] += count[i - 1]; //数据回放 for (i = n - 1; i >= 0; i--) array[--count[(temp[i] / d) % 10]] = temp[i]; }}void print(int array[], int n){ for (int i = 0; i < n; i++) cout << setw(6) << array[i]; cout << endl;}int main(){ cout << "******基数排序***by David***" << endl; int array[] = { 123, 234, 45, 111, 6, 128 }; int n = sizeof(array) / sizeof(int); cout << "原序列" << endl; print(array, n); cout << "基数排序" << endl; RadixSort(array, n); print(array, n); system("pause"); return 0;}
执行
转载请注明出处，本文地址：
若是有所帮助，顶一个哦！
专栏文件夹：