专注细节
努力进步

基数排序

基数排序也称为桶排序,是一种当关键字为整数类型时非常有效的排序方法。

基本思想如下:设待排序的数据元素关键字是m位d进制的整数,不足m位的高位补零,设置d个桶,令其编号分别为0,1,2,…,d-1。首先按关键字最低位的数值依次把各数据元素放到对应的桶中,这样按照桶号从小到大和进入桶中的先后顺序来一次收集分配在桶中的元素,这就是一次基数排序,同理进行接下来较高一位的排序,一直到第m次排序完成,那么就可以得到排好序的数据元素序列。

分析:算法中要求进出桶中的数据元素序列满足先进先出的原则,因此,这里所说的桶实际上就是队列,故我们代码中要设计一个链式队列(链表长度为d)。

我们这里使用stl里面的一些库,包括list、deque;这里遇到了一些小的问题,但是都一一解决了,熟悉了初始化vector设置大小LinQueue tub(d);选择vector而不是list是因为vector支持随机访问。

 

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
// 因为我们代码中需要用到随机访问,故我们这里使用vector
typedef vector< deque<int> > LinQueue;
#define DataType int
// n为排序数个数,m为数中最大数数位,d为进制类型与桶数一致
DataType* RadixSort(DataType a[], int n, int m, const int d){
int i,j,k,power=1;
LinQueue tub(d);

for(i=0;i<m;i++){
if(i==0)
power=1;
else
power=power*d;
//
for (j=0;j<n;j++)
{
//计算第j个数的第i位
k=a[j]/power%d;
tub.at(k).push_back(a[j]);
}
k=0;
for(j=0;j<d;j++){
while(!tub[j].empty()){

a[k]=tub.at(j).front();
tub[j].pop_front();
k++;
}
}

}
return a;

}
void display(DataType* a,int n){
for(int i=0;i<n;i++){
cout<<a[i]<<” “;
}
}

int main(){
DataType a[]={8,64,2,20,34,54,23,54,14,98};
DataType* aa=RadixSort(a,sizeof(a)/sizeof(int),2,10);
display(a,sizeof(a)/sizeof(DataType));
}

其中的at操作可以直接使用tub[j]。

点击下载代码文件

分享到:更多 ()