基数排序的原理、特点和完整代码实现。

基数排序（Radix Sort）

基数排序特点

• 是稳定排序
• 可用于链式结构，也可用于顺序结构
• 时间复杂度可以突破基于关键字比较一类方法的下界O(n log2 n)，达到O(n)
• 基数排序使用条件有严苛的要求：需要知道各级关键字的主次关系和各级关键字的主次范围

基数排序过程(原理)

算法思想

• 将整个关键字拆分为 d 位（或 “ 组 ”）
• 按照各个 关键字位 权重递增的次序（如：个、十、百），做 d 趟 分配 和 收集，若当前处理的关键字位可能取得r个值，则需要建立r个队列
• 分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应队列。一趟分配耗时O(n)
• 收集：把各个队列中的结点依次出队并链接。一趟收集耗时O®

性能

• 空间复杂度：O®
• 时间复杂度：O(d(n+r))
• 稳定性：稳

擅长处理

1. 数据元素的关键字可以方便地拆分为 d 组，且 d 较小
2. 每组关键字的取值范围不大，即r较小
3. 数据元素个数n较大

完整代码实现（顺序存储）

#include <iostream>
#include<string>
using namespace std;

// 获取数组中的最大值
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// 对数组按照指定位数进行计数排序
void countingSort(int arr[], int n, int exp) {
    // 创建一个临时数组用于存储排序结果
    int* output = new int[n];

    // 用于统计每个数字出现的次数，下标为0到9
    int count[10] = { 0 };

    // 统计该位上的数字出现次数
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // 计算累计频率
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 输出排序后的结果到output数组中
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 将排序结果拷贝回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    // 释放动态内存
    delete[] output;
}

// 基数排序
void radixSort(int arr[], int n) {
    // 获取数组中的最大值
    int max = getMax(arr, n);

    // 对每一位进行计数排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

int main() {
    int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "原数据: "<<endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    
    cout << endl;
    // 调用基数排序函数
    radixSort(arr, n);

    cout << "基数排序结果: " << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}

运行结果：

原数据:
170 45 75 90 802 24 2 66
基数排序结果:
2 24 45 66 75 90 170 802
请按任意键继续. . .

完整代码实现（链式存储）

注：此处选择使用静态链表和静态队列

#include <iostream>
#include<string>
using namespace std;

/*
    宏定义
*/
#define SIZE 9 //数组长度
#define RADIX 10 //关键字基数

/*
    静态链表
*/
struct Node{
    int key;    //节点对关键码值
    int next;   //下一节点在数组中的下标
};
/*
    静态队列
*/
struct StaticQueue{
    int front;   //队头指针
    int rear;   //队尾指针
};
/*
    根据关键字分配到队列
*/
void Distribute(Node* array, int first, int i, int r, StaticQueue* queue)
{
    for (int j = 0; j < r; j++)
    {
        queue[j].front = -1;
    }
    int curr = first;//取关键字
    while (curr != -1)
    {//对整个静态链进行分配
        int k = array[curr].key;
        for (int a = 0; a < i; a++)
        {//取第i位排序码数字k
            k = k / r;
        }
        k = k % r;
        if (queue[k].front == -1)
        {//把数据分配到第k个桶中
            queue[k].front = curr;
        }
        else
        {
            array[queue[k].rear].next = curr;
        }
        queue[k].rear = curr;
        curr = array[curr].next;//curr移动，继续分配
    }
}

/*
    收集：
       待收集数组：array 头结点：first 关键字基数：r  分配队列：queue
*/
void Collect(Node* array, int& first, int r, StaticQueue* queue)
{
    int k = 0;//已收集到的最后一个记录
    while (queue[k].front == -1)
    {//找到第一个非空队
        k++;
    }
    first = queue[k].front; //队列第k个元素的头结点赋值给first
    int last = queue[k].rear;//队列第k个元素的尾结点赋值给last
    while (k < r - 1) // k < 9
    {//继续收集下一个非空队列
        k++;
        while (k < r - 1 && queue[k].front == -1)// k < 9并且queue是空队列
        {
            k++;
        }
        if (queue[k].front != -1) //queue是非空队列
        {//试探下一个队列
            array[last].next = queue[k].front;
            last = queue[k].rear;//最后一个为序列的尾部
        }
    }
    array[last].next = -1;//收集完毕
}

/*
    按静态链表的地址排序
*/
void AddrSort(Node* array, int n, int first)
{
    int j = first;//j待处理数据下标
    Node TempRec;
    for (int i = 0; i < n - 1; i++)
    {//循环，每次处理第i个记录
        TempRec = array[j];//暂存第i个的记录array[j]
        swap(array[i], array[j]);
        array[i].next = j;//next链要保留调换轨迹j
        j = TempRec.next;//j移动到下一位
        while (j <= i)
        {//j比i小，则是轨迹，顺链找
            j = array[j].next;
        }
    }
}
/*
    基数排序：
        待排数组：array   
        数组长度：n  
        收集趟数：d  
        关键字基数：r
*/
void RadixSort(Node* array, int n, int d, int r)
{
    //头结点
    int first = 0;//first指向第一个记录
    //实例化队列
    StaticQueue* queue = new StaticQueue[r];
    //for (int i = 0; i < n - 1; i++)
    //{//初始化静态指针域
    //    array[i].next = i + 1;
    //}
    //array[n - 1].next = -1;//链尾next为空

    //对第i个排序码进行分配和收集，一共d趟
    /*
        i==0时，取个位数；i==1时，取十位数；i==2时，取百位数
    */
    for (int i = 0; i < d; i++)
    {
        Distribute(array, first, i, r, queue);
        Collect(array, first, r, queue);
    }
    delete[]queue;
    AddrSort(array, n, first);//按地址整理数据 
}

/*
    获取分配/收集次数
*/
int GetTurnNum(Node* array)
{
    //获取最大值
    int Max = array[0].key;
    int Num = 0;
    for (int i = 0; i < SIZE; i++)
    {
        if (array[i].key>Max)
        {
            Max = array[i].key;
        }
    }
    //计算收集次数
    for (int exp = 1; Max / exp > 0; exp *= 10) {
        Num++;
    }
    return Num;
}
/*
    内容输出方法：
        静态链表数组：Node* array
        数组长度：len
*/
void Print(Node* array,int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << array[i].key << " ";
    }
    cout << endl;
}

int main()
{
    //待排序静态链表型数组
    Node array[SIZE] = { {256, 1}, {170, 2}, {45, 3}, {75, 4}, {90, 5}, {802, 6}, {24, 7}, {2, 8}, {66, -1} };
    cout << "原序列：" << endl;;
    Print(array, SIZE);
    //分配/收集次数
    int Num = GetTurnNum(array);
    //基数排序
    RadixSort(array, SIZE, Num, RADIX);
    cout << "基数排序结果：" << endl;;
    Print(array, SIZE);
	system("pause");
	return 0;
}

运行结果：

原序列:
170 45 75 90 802 24 2 66
基数排序结果:
2 24 45 66 75 90 170 802
请按任意键继续. . .