C++编写经典算法之一:基数排序RadixSort(又称:桶子法BucketSort)(通俗易懂)
基数排序
- “基数排序”是数列排序的算法之一。
- 属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)。
- 基数,是同一类若干数据的集合,比如基数为个位数,那么个位数就是所有个位的数字的集合,通俗来说,你可以简单的理解为位数。
- “基数排序”通常有两种排序思路,一种是从低位到高位,称之为LSD(Least significant digital),相对的,另一种是从高位到低位,称之为 MSD (Most significant digital)。虽然看起来都是通过基数来进行排序的,但从低到高和从高到低的方法却是完全不同的,本文只展示比较简单的:LSD。
一、算法思路
首先我们要明白,在复数范围内,所有的数都是由0-9组成的,比较0-9就是我们在求学经历上,去比较两个数大小的最直观的判断。
在这里,我们将这十个基本的数字称之为“键值”。
假设我们有如图数列。
当基数为1时,即基数为个位数时,我们可以将数列中所有元素的个位数找出。
然后通过对比键值,将基数所代表的原数据,依次填入到键值组中。
最后,我们按键值从0到9的,将键值组中的数再次排列成一个新的数列。
如果我们利用同位素标记法标记出这次操作里进行关注的数字,可以发现我们这次操作中只对基数为1的数进行了排序。
- 其实通过这一次的操作,并没有完成排序。但如果继续观察,不难发现,我们已经对基数为1对数进行了部分排序,也就是说,我们可以保证:如果十位数相同,那么个位数必然十有序的。
然后,我们进行同样的操作。将基数设置为10.即十位数,将数列中所有元素的十位数找出。
同样的,通过对比键值,将基数所代表的原数据,依次填入到键值组中。
我们按键值从0到9的,将键值组中的数再次排列成一个新的数列。
利用同位素标记法标记出这次操作里进行关注的数字,可以发现我们这次操作中只对基数为10的数进行了排序。
- 我们不难发现,数列中所有的数字,都已经进行了排序,从而整个数列完成了排序。
整个过程如下:
二、代码清单及测试结果
#include <iostream>
#include <math.h>
#include <ctime>
template <class T>
/*
* 获取数组长度
*/
int getSizeOfArray(T& bs){
return sizeof(bs)/sizeof(bs[0]);
}
/*
* 获取数组中最大的数
*/
int getMaximumOfArray(int *rs,int size){
int max = rs[0];
for(int i=size-1;i>0;i--){
if(max<rs[i]){
max = rs[i];
}
}
return max;
}
/*
* 获取一个数的位数
*/
int getByteOfNumber(int number){
int byte = 0;
int consult = -1;//商
while(consult!=0){
consult = number/10;
byte++;
number = consult;
}
return byte;
}
/*
* 基数排序,利用LSD对数列进行排序
*/
void radixSort(int *rs,int size){
int radix = 1;//基数初始化
int max = getMaximumOfArray(rs,size);//最大值
int byte = getByteOfNumber(max);//最大值位数
int bucket[size];//初始化桶子(index代表键值)
int count[10];//初始化桶子元素计数器(记录键值行所含的元素个数)
int remainder[size];//初始化余数数列
int startIndex[10];//初始化键值的起始位数列
for(int i=1;i<=byte;i++){
//桶子元素计数器和键值的起始位数列每次使用前进行归位操作
for(int j=0;j<10;j++){
count[j] = 0;
startIndex[j] = -1;
}
//余数数列每次使用前进行清零操作
for(int j=0;j<size;j++){
remainder[j] = 0;
}
//计算键值行个数
for(int j=0;j<size;j++){
int re = (rs[j]/radix)%10;
remainder[j] = re;
count[re]++;
}
//利用桶子元素计数器计算各键值的起始位
int sum = 0;
for(int j=0;j<10;j++){
if(count[j]!=0){
startIndex[j] = sum;
sum += count[j];
}
}
//进桶
for(int j=0;j<size;j++){
bucket[startIndex[remainder[j]]] = rs[j];
startIndex[remainder[j]]++;
}
//出桶
for(int j=0;j<size;j++){
rs[j] = bucket[j];
}
//基数扩大
radix = radix * 10;
}
}
int main() {
using namespace std;
int rs[] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
int size = getSizeOfArray(rs);
// clock_t startTime,endTime;
cout<< "原数列:";
for(int i = 0;i<size;i++)
{
cout<< rs[i] << " ";
}
cout<< "\n" << "基数排序后:";
// startTime = clock();
radixSort(rs,size);
// endTime = clock();
for(int i = 0;i<size;i++)
{
cout<< rs[i] << " ";
}
// cout << "\n"<<"The run time is: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
return 0;
}
三、算法分析
“时间效率 :设待排序列为n个记录,d个关键码,关键码的取值范围为radix,则进行链式基数排序的时间复杂度为O(d(n+radix)),其中,一趟分配时间复杂度为O(n),一趟收集时间复杂度为O(radix),共进行d趟分配和收集。 空间效率:需要2*radix个指向队列的辅助空间,以及用于静态链表的n个指针。”
上述分析来自引用:
https://www.cs.auckland.ac.nz/software/AlgAnim/radixsort.html