文章目录
- 基数排序简介
- 基本原理
- LSD基本步骤
- MSD基本步骤
- 对于字符串使用基数排序
基数排序简介
基数排序是一种非比较型的排序算法，可以对整数或者字符串进行排序。
桶排序的一个好处是算法稳定。
基本原理
原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
MSD：先从高位开始进行排序，在每个关键字上采用桶排序
LSD：先从低位开始进行排序，在每个关键字上采用桶排序
LSD基本步骤
- 求出待排序字符串中最长字符串的长度，然后从低位到高位进行排序。
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
- 按照最低位的字符将字符串都分配到桶中，然后将每个桶中的每个数据都依次收集起来。
- 按照次低位的字符将字符串都分配到桶中，然后将每个桶中的每个数据都依次收集起来。
- 依次进行下去，直到所有的n位都处理完毕，得到一个有序的序列
一维数组实现方法
//c++
#include <bits/stdc++.h>
using namespace std;
int a[15];
void radixsort(int n)
{
int maxn=0;
//找到最大长度的数字
for(int i = 1;i <= n;i++)
{
string str = to_string(a[i]);
int len =str.length();
maxn = max(len,maxn);
}
int *tmp=new int[n+1];
int cot[10];
int radix=1;
for(int i = 1;i <= maxn;i++)
{
for(int j = 0;j < 10;j++)
{
cot[j]=0;
}
for(int j=1;j <= n;j++)
{
int k = (a[j]/radix)%10;
cot[k]++;
}
for(int j = 1;j < 10;j++)
{
cot[j]=cot[j]+cot[j-1];
}
for(int j=n;j>0;j--)
{
int k = (a[j]/radix)%10;
tmp[cot[k]--]=a[j];
}
for(int j = 1;j <= n;j++)
{
a[j]=tmp[j];
}
radix*=10;
}
delete []tmp;
}
int main(){
freopen("in.txt","r",stdin);
int n;
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
}
radixsort(n);
for(int i = 1;i <= n;i++)
{
cout << a[i] << endl;
}
return 0;
}
MSD基本步骤
MSD的基本步骤与LSD原理是相同的，只不过是从低位到高位进行排序。
- 求出待排序字符串中最长字符串的长度，然后从高位到低位进行排序。
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
- 按照最高位的字符将字符串都分配到桶中，然后将每个桶中的每个数据都依次收集起来。
- 按照次高位的字符将字符串都分配到桶中，然后将每个桶中的每个数据都依次收集起来。
- 依次进行下去，直到所有的n位都处理完毕，得到一个有序的序列
对于字符串使用基数排序
首先统一一下字符串大小的比较
1.从第0个位置开始比较。如果相同，继续往后比；
2.如果不同，则当前位置字符ASCII码大的对应字符串更大。
3.如果仍无法比较大小，则长度长的字符串更大，否则两者相等。
例如:
ABC>AACD
ABC>AB
ABC=ABC
不难看出字符串与数字的比较不同，因为字符串要考虑长度的问题。我认为有下面两种方法。(推荐第一种方法)
1.找到最长的字符串长度,然后将字符串的每个字符转为数字(str[i]-‘a’+1)存入一个临时数组ss中，然后为防止越界在ss后面补零直到到达最大字符串长度即可。
整个过程与数字的计算没有什么区别。代码不再补充
2.可以先将字符串长度当作最低有效位，因为基数排序是从最低有效位开始排的，就先用分配-收集算法对长度做一趟。后面就与第一种方法相似了。只要继续遍历每一位字符，直到最高位即可。
发布者：admin，转转请注明出处：http://www.yc00.com/web/1754939201a5217851.html
评论列表（0条）