桶式排序
讲基数排序之前，先讲一下桶式排序，二者有较大关联。
桶式排序是一种排序方式，比如说有N个整数，这N个整数范围从1~M（0~M-1也行)，则可以创建一个数组count，大小为M，将所有元素先初始化为0，每个元素称为一个桶，这个数组有M个桶。然后将要排序的数字逐个读入，假设读到A这个数字，则数组对应的元素count[A]的值加1，即桶记录了落入该桶的数据的个数。读完后，按顺序输出非0的桶的index(count[index]为多少则输出多少次)，输出的数据则是排序后的数据。
举个例子，将9、3、1、1、0、5这六个数据进行桶式排序，则建立个数组，因为数据最大值为9，则可取M=10(数组大小为10），建立数组count[10]，读入数据，先读入9，则count[9]=1,读入3，则count[3]=1,……count[1]=2,依此类推……，读完后，count[10]={1,2,0,1,0,1,0,0,0,1},数组中有些元素是为0的，将不为0的数据对应的序号输出来，元素为多少则输出多少次，输出为0、1、1、3、5、9，即为正确排序。
基数排序
基数排序是桶式排序的推广，当数据范围太大时所需要的桶会太多，所以采用多趟的桶式排序。怎么个多趟法，方法是低位优先桶式排序（也有高位优先排序），假设有一串数据
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
第二步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
第三步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
C++代码实现
#include "pch.h" #include <iostream> using namespace std; int maxbit(int data[], int n)//找出一组数据中的最大位数 { int count = 1; int d = 0; for (int i = 0; i < n; i++) { int temp = data[i]; while (temp / 10 != 0) { count++; temp = temp / 10; } if (d < count) d = count; count = 1; } return d; } void radixsort(int data[], int n)//进行基数排序 { int d = maxbit(data, n); //获取最大位数，即进行d次桶式排序 int *tmp = new int[n]; //tmp指向的空间用来存放为每次桶式排序后的数据 int *count = new int[10]; //count用来指向存放桶式排序后的落入各个桶的数字个数 int radix = 1; int j, k; for (int i = 1; i <= d; i++) { for (int i = 0; i < 10; i++) count[i] = 0; //每次分配前各个桶数据初始化为0 for (int i = 0; i < n; i++)//进行d次排序 { k = (data[i] / radix) % 10;//求出各个数据的某一位（个位、十位、百位…）是什么 count[k]++;//对应的桶内数据加1，即桶内放了多少个数 } for (j = 1; j < 10; j++)//目的是解决怎么将data数据按桶式顺序放到tmp所指空间中 count[j] = count[j - 1] + count[j]; for (int i = n-1; i>=0; i--)//把data里面的数据按排序后的顺序放入tmp所指空间，注意是从后面开始放数据 { k = (data[i] / radix) % 10; tmp[count[k] - 1] = data[i]; count[k]--; } for (int i = 0; i < n; i++)//把每次桶式排序后的数据给data data[i] = tmp[i]; radix *= 10; } delete[] tmp;//释放内存 delete[] count;//释放内存 } int main() { int data[10] = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 }; radixsort(data, 10); for (int i = 0; i < 10; i++)//输出排序后的数组数据 cout << data[i] << " "; system("pause"); return 0; }
运行结果：