C++实现基数排序的方法详解
C++实现基数排序的方法详解
发布时间:2016-12-28 来源:查字典编辑
摘要:基数排序(Radixsort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字...

基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。

它是这样实现的: 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。

(以上转自维基百科)

下面是我自己的实现,不足之处,还望指正:

复制代码 代码如下:

// RadixSort.cpp : 定义控制台应用程序的入口点。

#include "stdafx.h"

#include <iostream>

using namespace std;

//定义队列的节点

struct Node

{

int data;

Node* next;

};

//定义程序所需的特殊队列

class Queue

{

public:

Queue()

{

Node* p = new Node;

p->data = NULL;

p->next = NULL;

front = p;

rear = p;

}

~Queue()

{

Node* p = front;

Node* q;

while (p)

{

q = p;

p = p->next;

delete q;

}

}

//在队列的尾部添加一个元素,节点不存在,需要程序创建

void push(int e)

{

Node* p = new Node;

p->data = e;

p->next = NULL;

rear->next = p;

rear = p;

}

//在队列的尾部添加一个节点,节点原来就存在

void push(Node* p)

{

p->next = NULL;

rear->next = p;

rear = p;

}

//数据元素中最大位数

int lenData()

{

int temp(0);//数据元素的最大位数

int n(0); //单个数据元素具有的位数

int d; //用来存储待比较的数据元素

Node* p = front->next;

while (p != NULL)

{

d = p->data;

while (d > 0)

{

d /= 10;

n++;

}

p = p->next;

if (temp < n)

{

temp = n;

}

n = 0;

}

return temp;

}

//判断队列是否为空

bool empty()

{

if (front == rear)

{

return true;

}

return false;

}

//清除队列中的元素

void clear()

{

front->next = NULL;

rear = front;

}

//输出队列中的元素

void print(Queue& que)

{

Node* p = que.front->next;

while (p != NULL)

{

cout << p->data << " ";

p = p->next;

}

}

//基数排序

void RadixSort(Queue& que)

{

//定义一个指针数组,数组中存放十个分别指向十个队列的指针

Queue* arr[10];

for (int i = 0; i < 10; i++)

{

arr[i] = new Queue;

}

int d = 1;

int m = que.lenData(); //取得待排序数据元素中的最大位数

//将初始队列中的元素分配到十个队列中

for(int i = 0; i < m; i++)

{

Node* p = que.front->next;

Node* q;

int k; //余数为k,则存储在arr[k]指向的队列中

while (p != NULL)

{

k = (p->data/d)%10;

q = p->next;

arr[k]->push(p);

p = q;

}

que.clear(); //清空原始队列

//将十个队列中的数据收集到原始队列中

for (int i = 0; i < 10; i++)

{

if (!arr[i]->empty())

{

Node* p = arr[i]->front->next;

Node* q;

while (p != NULL)

{

q = p->next;

que.push(p);

p = q;

}

}

}

for (int i = 0; i < 10; i++)//清空十个队列

{

arr[i]->clear();

}

d *= 10;

}

print(que); //输出队列中排好序的元素

}

private:

Node* front;

Node* rear;

};

int _tmain(int argc, _TCHAR* argv[])

{

Queue oldque;

int i;

cout << "Please input the integer numbers you want to sort.Input ctrl+z to the end:" << endl;

while (cin >> i)

{

oldque.push(i);

}

oldque.RadixSort(oldque);

cout << endl;

return 0;

}

下面的代码转自维基百科,还没仔细分析,先拿过来

复制代码 代码如下:

#include <iostream>

using namespace std;

const int base=10;

struct wx

{

int num;

wx *next;

wx()

{

next=NULL;

}

};

wx *headn,*curn,*box[base],*curbox[base];

void basesort(int t)

{

int i,k=1,r,bn;

for(i=1;i<=t;i++)

{

k*=base;

}

r=k*base;

for(i=0;i<base;i++)

{

curbox[i]=box[i];

}

for(curn=headn->next;curn!=NULL;curn=curn->next)

{

bn=(curn->num%r)/k;

curbox[bn]->next=curn;

curbox[bn]=curbox[bn]->next;

}

curn=headn;

for(i=0;i<base;i++)

{

if(curbox[i]!=box[i])

{

curn->next=box[i]->next;

curn=curbox[i];

}

}

curn->next=NULL;

}

void printwx()

{

for(curn=headn->next;curn!=NULL;curn=curn->next)

{

cout<<curn->num<<' ';

}

cout<<endl;

}

int main()

{

int i,n,z=0,maxn=0;

curn=headn=new wx;

cin>>n;

for(i=0;i<base;i++)

{

curbox[i]=box[i]=new wx;

}

for(i=1;i<=n;i++)

{

curn=curn->next=new wx;

cin>>curn->num;

maxn=max(maxn,curn->num);

}

while(maxn/base>0)

{

maxn/=base;

z++;

}

for(i=0;i<=z;i++)

{

basesort(i);

}

printwx();

return 0;

}

推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关阅读
网友关注
最新C语言学习
热门C语言学习
编程开发子分类