基数排序是一种数据格式相关的算法，适用范围有限，当数据位数较小时，基数排序法的时间复杂度近似为O...
基数排序是一种数据格式相关的算法，适用范围有限，当数据位数较小时，基数排序法的时间复杂度近似为O(n)，效率高于其它的稳定性排序算法。
1. 算法思想
以十进制数为例，现将元素按个位出入一次基数桶，再按十位出入基数桶……直至按最高位出入基数桶，此时序列整体有序。
2. 时间复杂度
最好情况 O(d*(n + r))：d是数据位数，r是基数，如十进制即为10最坏情况 O(d*(n + r))：与待排序列的元素顺序无关
3. 空间复杂度 O(n + r)
需要r个链表指针，以及所有链表共存储n个元素
4. 稳定性
稳定。出入链表都是按原始顺序的，而且同值元素始终进入到相同的链表
5. 代码实现（伪代码）
因为涉及链表操作，如果带上链表实现过于冗长，因此只列出伪代码void RadixSort(int *A, int n){ int radix = 10; int bits = 所有元素最大位数; Table *tbl = (Table *)malloc(radix * sizeof(Table)); for (int i = 0; i < bits; ++i) { for (int j = 0; j < n; ++j) { int idm = A[j]的第i位; 将A[j]插入链表tbl[idm]; } j = 0; for (int k = 0; k < radix; ++k) { while (tbl[k] != NULL) { A[j++] = tbl[k]->data; tbl[k] = tbl[k]->next; } } }}版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：算法笔记--归并排序 下一篇：CC2640R2F I2C驱动
