1.数据结构学习之基数排序（含C++代码）
1.1.概念 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
1.2.基本解法
1.2.1第一步
以下面的一列数为例，假设原来有一串数值如下所示：
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
1.2.2第二步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
【数据结构|数据结构学习之基数排序（含C++代码）】0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
1.2.3第三步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
代码如下：
/*算法：基数排序*/
#include
using namespace std;
/*********************************************************
Function:rxsort
Description:基数排序
Input:
数组A[l,h]；
数组中最大元素的位数d，例如最大数为999，则d为3；
进制数k，如果是10进制数，k为10；
Output:排序好的数组；
Others：对数字1234来说，预定第0位为4，第1位为3，依次类推；
*********************************************************/
bool rxsort(int A[],int l,int h,int d,int k){
if(NULL==A||l>h)
return false;
int size = h-l+1;
int* counts = new int[k];
//用于计数排序的辅助数据，详见计数排序
int* temp = new int[size];
//用于存储重新排序的数组
int index;
int pval=1;
//依次处理不同的位
for(int i=0;
i=l;
j--){
index = (int)(A[j]/pval)%k;
temp[counts[index]-1] = A[j];
counts[index]--;
}
//将按第i为数排序后的结果保存回数组A中
for(int j=0;
j
运行结果如下：
文章图片
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 个人日记|K8s中Pod生命周期和重启策略
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 学习分享|【C语言函数基础】
- C++|C++浇水装置问题
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- C++|从零开始学C++之基本知识