C++基数排序(包含计数排序)
1、hanshu.h //自定义头文件
#define N1 10
#define N2 1000
struct Node
{
int value; //排序元素值
int subDigit;//排序值除去地位
int digitValue;//每位值,如个位值,十位值
int digitSum;// 此元素的位数
};
int GetMaxDigitNum(const Node *node,const int n); //头文件函数声明
int GetDigitNum(const Node node);
void CountDigitSort(Node *node1,Node *node2,int *count,int n);
2、hanshu.cpp//自定义源文件,函数实现
#include"stdafx.h"
#include"hanShu.h"
#include<iostream>
using namespace std;
int GetMaxDigitNum(const Node *a,const int n)//得到所有输入的需要排序的元素的最大位数,如1111,四位
{
int num;
int max=0,sum=0;
int i =0;
for(i=0;i<n;i++)
{
num=a[i].value;
sum = 0;
while(num)
{
num/=10;
sum++;
}
if(max<sum)
max=sum;
}
return max;
}
int GetDigitNum(const Node node) //得到每个输入元素的位数
{
int num;
int sum=0;
num=node.value;
if(num==0)
sum =1;
while(num)
{
num/=10;
sum++;
}
return sum;
}
void CountDigitSort(Node *node1,Node *node2,int *count,int n) //计数排序,从个位开始,元素某位没有的就补0,此需要稳定排序
{
int i = 0;
for(i=0;i<N1;i++)
count[i]=0;
for(i=0;i<n;i++)
count[node1[i].digitValue]+=1;
for(i=1;i<N1;i++)
count[i]+=count[i-1];
//for(i=0;i<N1;i++)
//cout<<count[i]<< " ";
//cout<<endl;
for(i=n-1;i>=0;i--)
{
node2[count[node1[i].digitValue]-1] = node1[i];
count[node1[i].digitValue]--;
}
for(i=0;i<n;i++)
cout<<node2[i].value<< " ";
cout<<endl;
}
3、main() //main()函数
#include "stdafx.h"
#include "hanShu.h"
#include<iostream>
using namespace std;
Node nodes[N2],sortNodes[N2]; //nodes[] 存储需要排序的元素,sortNodes[]存储排序后的元素
int count[N1];
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入排序案例的个数:"<<endl;
cin>>cases;
while(cases--)
{
cout<<"请输入你需要排序的元素的个数:"<<endl;
int n;
cin>>n;
int i,j;
cout<<"请输入你需要排序的元素:"<<endl;
for(i=0;i<n;i++)
{
cin>>nodes[i].value;
nodes[i].subDigit = nodes[i].value;
nodes[i].digitSum = GetDigitNum(nodes[i]);
cout<< nodes[i].digitSum << " ";
}
cout<<endl;
int digitSum;
digitSum = GetMaxDigitNum(nodes,n);
cout<<digitSum<<endl;
for(i=1;i<=digitSum;i++)
{
if(i>1)
{
for(j= 0;j<n;j++)
nodes[j]=sortNodes[j];
}
for(j=0;j<n;j++)
{
if(nodes[j].digitSum>=i)
{
nodes[j].digitValue = nodes[j].subDigit%10;
nodes[j].subDigit/=10;
}
else
nodes[j].digitValue =0 ;
}
//cout<<"K"<<endl;
//for(int k = 0;k<n;k++)
//cout<<nodes[k].digitValue<<" ";
CountDigitSort(nodes,sortNodes,count,n); //分别按个位,十位,百位...排序
}
for(i=0;i<n;i++) //输出排序后的个元素
cout<<sortNodes[i].value<<" ";
cout<<endl;
}
system("pause");
return 0;
}
分享到:
相关推荐
C++写基数排序算法,数据结构课的上机题代码
基数排序基数排序基数排序基数排序基数排序
该算法用C++语言实现了基数排序算法,已经调试通过,在Linux系统环境中运行结果正常
C实现基数排序,代码简练,清洗易懂,欢迎下载,有问题的地方请CSDN上给我留言加以修正,共勉。
C++ 基数排序 大家好,今天带来的是自己实现的用C++完成基数排序.在数据结构,算法分析和程序设计的学习过程中,我们经常也无法避免的要学到排序的算法.排序算法是程序设计过程中使用频率极高的算法之一,其输入是一组...
算法导论之基数排序,桶排序。基数排序是利用在各个位上进行计数排序,是一种线性排序
简单的十大排序,c++代码实现,堆,冒泡,快速,计数,基数,归并,简单排序等
计数排序 用C++实现 简单易懂 欢迎下载
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
通过c++语言实现了基数排序的算法,方法巧妙,容易理解,运行无误。
时间复杂度达到O(n)的不同于sort给予比较的O(nlogn)排序,是基于计数的一种线性排序方法,效率非常优秀。
O(n)时间完成,是排序中性能最好的!适用于初学者以及有一定水平的学生哦!!!
基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于...
快速排序
c++编写的基数排序 代码简洁 简单易懂 用队列实现队列的应用
用C++实现冒泡排序 快速排序 插入排序 基数排序 希尔排序 归并排序 选择排序
数据结构 基数排序算法 有C++程序
C++ 希尔排序实现
课程设计--基数排序c++源代码,报告齐全。