C++实现基数排序的方法详解
更新时间:2020年4月25日 17:46 点击:1746
基数排序(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;
}
它是这样实现的: 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
基数排序的方式可以采用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++中virtual继承的深入理解
下一篇: 如何用C++实现双向循环链表
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25