一、基数排序
基数排序是一种非比较型整数排序算法，也称桶排序，它的基本思想是通过对数据的每一位进行排序，低位优先，从最低位到最高位依次进行进桶出桶操作，循环count次（count为最大值的位数)，最终实现整个数据序列的有序排列。
桶排序不能处理负数。
1.算法思想
算法原理
- 基数排序是基于桶排序的思想，将整数按位数切割成不同的数字，然后按每个位数分别进行排序。
- 对于每个位数，使用稳定的排序算法（如计数排序）将元素分配到不同的桶中，然后再按顺序收集桶中的元素。
- 从最低位开始，依次对每一位进行上述操作，直到最高位处理完毕，此时整个序列就有序了。
进桶：
出桶：
以此类推。
十位：
百位：
2.代码实现
//基数排序static int GetFigur(int* arr, int len)
{int max = arr[0];for (int i = 0; i < len; i++){if (max < arr[i]){max = arr[i];}}//求位数//丢个位int count = 0;while (max != 0){count++;max /= 10;}return count;
}
//获取十进制整数右数第figur位的数，figur从0开始
static int GetNum(int n, int figur)
{for (int i = 0; i > figur; i++){n /= 10;}return n % 10;
}void RadixSort(int* arr, int len)
{//定义10个队列HNode queArr[10];for (int i = 0; i < 10; i++){InitQueue(&queArr[i]);}//得到最大数字的位数，确定进队和出队的趟数int count = GetFigur(arr, len);int index;//队列的下标for (int i = 0; i < count; i++){//入队for (int j = 0; j < len; j++)//遍历数组入队{index = GetNum(arr[j], i);//index保存arr[j]进入队列的下标Push(&queArr[index], arr[j]);}//依次出队int j = 0;//arr的下标for (int k = 0; k < 10; k++){while(!IsEmpty(&queArr[k])) {Pop(&queArr[k], &arr[j++]);}}}for (int i = 0; i < 10; i++){Destroy(&queArr[i]);}
}
3.复杂度分析
时间复杂度：O(d*n) d为最大数据的位数
空间复杂度：桶排序需要额外的空间来存储桶和桶内元素，空间复杂度为O(n)。
稳定性：桶排序是稳定的排序算法。在桶排序过程中，每个桶内的元素在排序时会保持相对顺序不变。例如，对于相同大小的元素，先进入桶的元素会先被处理，从而保证了它们在排序后的相对顺序与原始序列一致。
二、八大排序总结
| 排序 | 算法描述 | 时间复杂度 | 备注 | 空间复杂度 | 备注 | 稳定性 | 备注 |
| 插入排序 | 类似整理扑克牌插牌，将数据分为已排序部分和未排序部分，开始时将第一个元素默认已排序，从未排序部分中依次取数据将其与已排序部分从后往前比较，如果待排序数字小于已排序的数据，则将已排序数据依次后移一位，在合适位置插入待排序数字 | 最好情况O(n)，最坏情况（数组逆序）O(n2) | 越有序越快，一组数据基本有序的情况下使用插入排序 | O(1) | 稳定 | 适用于小规模数据的排序 | |
| 希尔排序 | 对插入排序的一个改进，因为插入排序越有序越快，则为了使数据尽量有序，使用间隔式分组方法将原始数据分为若干子序列，对每个子序列进行插入排序，然后逐渐减小子序列的元素间隔，直至间隔为1，此时整个序列基本有序，最后进行一次插入排序即可 | 平均时间复杂度估计值为O(n1.3) | 重点在于间隔式排序，不同间隔序列下算法性能波动明显 | O(1) | 原地排序算法 | 不稳定 | 多处理大规模数据 |
| 冒泡排序 | 相邻两个元素两两比较，大的往后走，多次遍历 | O(n2) | O(1) | 稳定 | 不适用于大规模数据 | ||
| 选择排序 | 每次都从待排序部分中选出最小的和未排序部分的第一个数据交换，从而将该元素添加到已排序部分的末尾，已排序部分初始为空 | O(n2) | O(1) | 不稳定 | 可能会改变相同元素的相对顺序 | ||
| 快速排序 | 从数据中选一个基准值，经典快排选择第一个元素，定义两个指针分别指向序列的头和尾，先从尾指针开始与基准比较，找第一个比基准小的数字，头指针找第一个比基准大的数字，交换头尾指针指向的数字，直到头尾指针相遇，相遇位置则为基准元素的位置，此时基准元素有序，递归排序左右两部分子序列，直至子序列长度为1或0 快速排序优化主要优化越有序越慢的问题，1.随机选择基准值；2.选择头、尾、中间值三个数的中位数作基准值3.小数组直接使用插入排序 | 平均时间复杂度O(nlogn),最坏情况下是O(n2) | 因为递归；越有序越慢，完全有序退化为选择排序 | 平均为O(logn),最坏情况下是O(n) | 使用递归会用到栈保存数据 | 不稳定 | |
| 堆排序 | 使用二叉树的结构，先把数据构建成大根堆（从最后一个非叶子节点开始比较父节点与左右孩子结点的值，将父结点与较大值交换），再将最后一个元素与根结点交换位置（即从大到小依次有序），取出该元素放入已排序序列末尾，之后重新调整堆，直到堆只剩下一个元素，此时整个数组有序 调整大根堆：从最后一棵子树开始从后往前调整 | 建立大根堆为O(n);调整（n-1次）大根堆总的时间复杂度为O(nlogn);平均为O(nlogn) | O(1) | 堆排序直接在原数组上操作 | 不稳定 | 交换堆顶元素与最后一个元素 | |
| 归并排序 | 一组数据先看作每个元素单独有序，将两端有序的子序列合并为一段有序的，递归操作，直到整个数组有序 | 平均为O(nlogn) | logn层递归操作 | O(n) | 需要临时数组来存放数据 | 稳定 | 常使用于外部排序 |
| 基数排序 | 也称桶排序，借助每个数据的每一位的大小排序，依次进桶出桶，先排个位、十位、百位直至最大数字的位数，排完最大位数则整组数据有序 注意，桶排序不能处理负数 | O(d*n) | d为最大数据的位数且每个数位上的取值范围是固定的（如 0 - 9） | O(n) | 需要额外的空间来存储桶和桶内元素 | 稳定 | 基数排序对数据的分布有一定要求，若数据的位数差异过大，可能会影响算法性能 |
