精华内容
下载资源
问答
  • 基数排序C++实现

    2021-04-13 13:58:33
    10.基数排序基数排序的基本思想基数排序的算法步骤C++代码实现 基数排序的基本思想 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符...

    基数排序的基本思想

    1. 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
    2. 基数排序的发展:(计数→桶→基数排序)
      计数排序:每个桶只存储单一键值;
      桶排序:每个桶存储一定范围的数值;
      基数排序:根据键值的每位数字来分配桶。

    静态图解:

    1. 按照个位数进行排序;
    2. 按照十位数进行排序;
    3. 按照百位数进行排序,此时序列有序。

    在这里插入图片描述

    基数排序的算法步骤:

    获取序列A最大值并确定最大位数,从个位开始,按位进行桶排序(调用基数排序子函数):

    1. 初始化10个桶bucket和临时数组result
    2. 遍历序列A,将数据出现的次数存在相应的桶bucket中;
    3. 调整桶bucket中各元素的值,调整后的值就是待排序列A中元素在result中的位置;
    4. 将待排序列元素填入result中(后入先出顺序);
    5. result全部排好后,将其复制回待排序列A

    动态图解:

    在这里插入图片描述

    C++代码实现

    #include "pch.h"
    #include <iostream>
    #include <time.h>
    using namespace std;
    
    /*排序方法类*/
    class MySort {
    public:
    	int n;
    	int* A;
    	//构造函数 ,便于挑选不同的排序方法
    	MySort(int N) {
    		this->n = N;
    		A = new int[this->n];
    		this->SetArray();
    	}
    	//随机初始化数组 
    	void SetArray() {
    		srand(time(0));
    		for (int i = 0; i < n; i++) {
    			A[i] = rand() % 100 + 1;
    		}
    	}
    	//打印数组 
    	void Print() {
    		for (int i = 0; i < n; i++) {
    			cout << A[i] << " ";
    		}
    		cout << endl;
    	}
    
    	//基数排序主函数
    	void radixsort(int* A, int n) {
    		int imax = 0;      //获取数组中的最大键值
    		for (int i = 0; i < n; i++)imax = imax > A[i] ? imax : A[i];
    		for (int iexp = 1; imax / iexp > 0; iexp *= 10)  
    			_radixsort(A, n, iexp);    //从个位开始,对数组A按位进行基数排序
    	}
    	//按位排序子函数
    	void _radixsort(int *A, int n, int exp) {
    		int *result = new int[n];    //存放桶中收集数据后的临时数组
    		int bucket[10] = { 0 };    //初始化10个桶
    		//遍历A,将数据出现的次数存储在桶bucket中
    		for (int i = 0; i < n; i++)
    			bucket[(A[i] / exp) % 10]++;
    		//调整bucket各元素的值,调整后的值就是A中元素在result中的位置
    		for (int i = 1; i < 10; i++)
    			bucket[i] = bucket[i] + bucket[i - 1];
    		//将A中的元素填充到result中(从后往前排,先入后出)
    		for (int i = n - 1; i >= 0; i--) {
    			int iexp = (A[i] / exp) % 10;
    			result[bucket[iexp] - 1] = A[i];
    			bucket[iexp]--;
    		}
    		//将排序好的数组result复制回A中
    		memcpy(A, result, n * sizeof(int));
    	}
    };
    
    int main() {
    	//初始化数组 
    	int N;
    	cout << "请输入数组长度:";
    	cin >> N;
    	MySort sort1(N);   //构造排序方法类
    	cout << endl;
    	cout << "基数排序前:";
    	sort1.Print();
    	sort1.radixsort(sort1.A,N);      //基数排序
    	cout << "基数排序后:";
    	sort1.Print();
    	cout << endl;
    	return 0;
    }
    
    

    代码验证:

    在这里插入图片描述

    展开全文
  • 基数排序 C++

    2021-04-23 16:19:32
    C++代码如下(仅练习使用,若有错误,望友友们指正,多谢!) #include<iostream> using namespace std; int getKNum(int a,int k)//获取个十百位上的值 { int n=a; int t=1; for(int j=1;j<=k;j++) { ...

    C++代码如下(仅练习使用,若有错误,望友友们指正,多谢!)

    #include<iostream>
    using namespace std;
    int getKNum(int a,int k)//获取个十百位上的值
    {
        int n=a;
        int t=1;
        for(int j=1;j<=k;j++)
        {
            t*=10;
        }
        int x=(a/t)%10;
        return x;
    }
    void CountSort(int *a,int n,int k)//每次循环的计数排序
    {
        int temp[10]={0};
        int p[n]={0};
        for(int i=0;i<n;i++)
        {
            p[i]=a[i];//先把a复制给p
        }
        for(int i=0;i<n;i++)
        {
            int r=getKNum(a[i],k);//获取a[i]的k位数的值,如果k=1,则获取的是十位
            temp[r]++;//k位为r的增加
        }
        for(int i=1;i<10;i++)
            temp[i]+=temp[i-1];//不大于i的共有多少
        for(int i=n-1;i>=0;i--)
        {
            int h=getKNum(p[i],k);
            a[temp[h]-1]=p[i];//从最后一个元素p[i](a[i])开始往前
            temp[h]--;//对于相等元素的处理
        }
    }
    int GetMaxNum(int *a,int n)//获取循环的次数,也就是最大值有几位循环几次
    {
        int mmax=-1;
        for(int i=0;i<n;i++)
        {
            if(a[i]>mmax)
            {
                mmax=a[i];
            }
        }
        int x=mmax;
        int t=0;
        while(x)
        {
            t++;
            x/=10;
        }
        return t;
    }
    void RadixSort(int *a,int n,int &e)//基数排序
    {
        int num=GetMaxNum(a,n);
        e=num;
        for(int i=0;i<num;i++)
        {
            CountSort(a,n,i);
        }
    }
    int main()
    {
        int a[10]={123,1,23,45,67,89,65,23,111,3333};
        int x=0;
        int n=10;
        for(int i=0;i<10;i++)
            cout<<a[i]<<" ";
        cout<<endl;
         RadixSort(a,10,x);
         cout<<x<<endl;
        for(int j=0;j<n;j++)
          {
               cout<<a[j]<<"  ";
          }
    }
    
    展开全文
  • C实现基数排序,代码简练,清洗易懂,欢迎下载,有问题的地方请CSDN上给我留言加以修正,共勉。
  • 基数排序_RADIXSORT

    2015-05-19 17:32:07
    基数排序的排序工作在线性时间之内就可以完成,速度非常之快,这里给出了基于计数排序和桶排序的两种类型的基数排序算法
  • 基数排序c++实现

    2019-12-23 15:36:21
    增加空间优化了桶内排序的过程,十进制例子就有十个桶,先个位排序一遍,再十位进桶到最高位时则是排好序的。 int Maxbit(int A[], int n)//求待排序序列最大元素位数 { int maxvalue = A[0], digits = 0;//初始化...

    增加空间优化了桶内排序的过程,十进制例子就有十个桶,先个位排序一遍,再十位进桶到最高位时则是排好序的。

    int Maxbit(int A[], int n)//求待排序序列最大元素位数
    {
    	int maxvalue = A[0], digits = 0;//初始化最大元素为A[0],最大位数为0
    	for (int i = 1; i < n; i++) //找到序列中最大元素
    		if (A[i] > maxvalue)
    			maxvalue = A[i];
    	while (maxvalue != 0)//分解得到最大元素的位数
    	{
    		digits++;
    		maxvalue /= 10;
    	}
    	return digits;
    }
    
    int Bitnumber(int x, int bit)//求x第bit位上的数字,例如238第2位上的数字为3
    {
    	int temp = 1;
    	for (int i = 1; i < bit; i++)
    		temp *= 10;
    	return (x / temp) % 10;
    }
    
    void RadixSort(int A[], int n)//基数排序
    {
    	int i, j, k, bit, maxbit;
    	maxbit = Maxbit(A, n);//求最大元素位数
    	int **B = new int *[10];
    	for (i = 0; i < 10; i++)
    		B[i] = new int[n + 1];
    	for (i = 0; i < 10; i++)
    		B[i][0] = 0;//统计第i个桶的元素个数
    	//从个位到高位,对不同的位数进行桶排序
    	for (bit = 1; bit <= maxbit; bit++)
    	{
    		for (j = 0; j < n; j++)//分配
    		{
    			int num = Bitnumber(A[j], bit);//取A[j]第bit位上的数字
    			int index = ++B[num][0];
    			B[num][index] = A[j];
    		}
    		for (i = 0, j = 0; i < 10; i++)//收集
    		{
    			for (k = 1; k <= B[i][0]; k++)
    				A[j++] = B[i][k];
    			B[i][0] = 0;//收集后元素个数置零
    		}
    	}
    	for (int i = 0; i < 10; i++)
    		delete[]B[i];
    	delete B;
    }
    int main() {
    	int r[5] = {1,5,3,4,2};
    	RadixSort(r, 5);
    	for (int i = 0; i < 5; i++)
    	{
    		cout << r[i] << " ";
    	}
    	return 0;
    }
    
    展开全文
  • //20个桶, tank[x][i]表示当前位是x的第i个数,这里tank[x][0]表示tank[x]这个数组有多少个元素,故存数据时从tank[x][1]开始存 //基数排序(基数就对应着 进制数) void radixSort(){ int k = 1, d = 1; //k是最大...

    Theory:

    ​ 从低位到高位, 每次分两步:

    1. 把当前位相同的数放在同一个桶里面,如个位数都是1的就都放到1号桶

    2. 从[0, radix - 1]把每个桶里面的数按顺序收集起来(radix是数的进制,也是桶的个数,如十进制数 radix就是10)

    然后循环执行上述步骤k次,其中k是所有数中最大的数位

    Attention:

    1. 如果全是非负数,那么只需要开radix个桶;
    2. 有负数时开20个(这里是对于十进制数), 因为有 -ab % 10 = -b,把[-9, -1]映射到[1, 9],把[0, 9]映射到[10, 19] (即加上10)

    Code:

    int a[7] = {1, 0, 1, 8, -1, 0, -1}, n = 7;         //测试数据
    
    int tank[20][100];         //20个桶, tank[x][i]表示当前位是x的第i个数,这里tank[x][0]表示tank[x]这个数组有多少个元素,故存数据时从tank[x][1]开始存
    
    //基数排序(基数就对应着 进制数)
    void radixSort(){       
        int k = 1, d = 1;        //k是最大位数,d是当前位的权重,即1, 10, 100.....
        
        //计算最大位数, 公式 k = (int)log10(x) + 1,注意x要大于0
        for(int i = 0; i < n; i++) 
    		if(a[i])        //非零时, 计算 |a[i]| 的位数
                k = max((int)log10(abs(a[i])) + 1, k);
    	
    	while(k--){            //循环k次
    		memset(tank, 0, sizeof(tank));        //每次循环先把tank清零
    		
    		for(int i = 0; i < n; i++){        //枚举n个数
    			int x = a[i] / d % 10 + 10;		 //得到当前位的值x(记得要加10)
    			tank[x][++tank[x][0]] = a[i];     //放到第x个桶里面,注意是++tank[x][0]
    		}
    		
    		int cnt = 0;
    		for(int i = 0; i < 20; i++)       //枚举20个桶
                //依次拿出每个桶里面的值[1, tank[i][0]], 注意取出顺序和放入顺序是一样的(类似队列,先进先出),故基数排序稳定
    			for(int j = 1; j <= tank[i][0]; j++)   
    				a[cnt++] = tank[i][j];        //回收
    		d *= 10;        //权重 * 10
    	} 
    }
    

    如果此篇文章对你有帮助,点个👍啦!

    在这里插入图片描述

    展开全文
  • C++基数排序

    2020-11-21 23:28:53
    基数排序也是分配排序: 以下面的这个数组作为例子 以上面的例子来说,要将他排序的话,首先基数排序的思想,可以按照数值的个位数的大小先排一次序,并且按照顺序将数据给记录下来,然后再将数值的十位拍一次序,...
  • 基数排序c++

    2020-03-28 16:26:51
    思想:不是比较也不是移动而是根据关键字 两个要点: 基;序列中数的最大位数,个位,十位,百位,, 桶:0-9 基本步骤: ... for:遍历数组a,计算当前位数的值b,放到对应的桶里bucket[b]=a ...iostre...
  • 基数排序 c++实现

    2017-12-21 17:20:10
    基数排序是一个稳定的排序,其效率与位数有关,且消耗多余等大的空间来存放数组
  • 基数排序C/C++代码实现

    千次阅读 2020-07-08 17:24:28
    链式基数排序: 分配类排序不需要比较关键字的大小,它 是根据关键字中各位的值,通过对待排序记录进行若干趟 “ 分配 ” 与 “ 收集” 来实现排序的,是一种 借助于多关键字排序的思想对单关键字排序的方法。基数...
  • 排序 基本思想 先扫描得到待排序数组中的最大值maxVal与最小值minVal,假设桶的个数为k,则代表则将[minVal, maxVal]均分为k个范围,每个范围中的元素各自放入对应的桶中。如此桶之间必然是有序的,桶内使用排序...
  • 设计一个将一组英文单词按字典序排列的基数排序算法。设单词均由小写字母或空格构成,最长的单词有n个字母
  • 基数排序是一种非比较型整数排序算法,其原理是将众多数字按位分隔后进行排序。 实现步骤: 1.将所有待比较的数字(正整数)统一为同一长度,位数不够的数字前面补0; 2.按照从个位,十位,百位······从低到高...
  • 基数排序:属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定...
  • 实验二 排序算法 要求完成时间 实验开始后的第三周之前完成...数字选择排序方法,1-冒泡排序、2-插入排序、3-基数排序。 使用所选排序方法的排序,结果输出所用方法以及结果,每个数之间用“,”隔开,中间不要有空格。
  • #include<iostream> #include<cmath> #include<queue> using namespace std; int main() { int numbers[11]={10,34,23,112,32,54,234,110,11220,9430,1234}; queue<... ...
  • 基数排序C++实现

    千次阅读 2015-08-24 19:56:38
    基数排序介绍 基数排序(Radix Sort)是桶排序的扩展,它的基本思想是:将整数按位数切割成不同的数字,然后按每个位数分别比较。 具体做法是:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,...
  • 基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于...
  • C++实现基数排序(radix sort)

    千次阅读 2017-01-23 21:44:44
    但是一些排序不基于比较的可以达到线性时间,称为线性时间排序(Linear-Time Sort),比如桶排序(Bucket Sort)和基数排序(Radix Sort)。桶排序比较简单,基数排序相当于通过循环进行了多次桶排序。基数排序的原理可以...
  • 很久之前学习过基数排序当时觉得麻烦没有仔细看,现在回过头来发现这个东西其实挺有意思的,现在搞明白了LSD就是从小到大排列的(对于数据的处理从右边最低位开始),但是对于MSD(对于数据的处理从左边最高位开始)我还...
  • C++ 基数排序  大家好,今天带来的是自己实现的用C++完成基数排序.在数据结构,算法分析和程序设计的学习过程中,我们经常也无法避免的要学到排序的算法.排序算法是程序设计过程中使用频率极高的算法之一,其输入是一组...
  • 1.数据结构学习之基数排序(含C++代码) 1.1.概念 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的...
  • 步骤 将各待比较元素数值统一数位长度,即对数位短者在前补零; 根据个位数值大小,对数组进行排序; ...重复上一步骤,依次根据更...// 基数排序 (只适用于正数,此处不适用) void radixSort(vector&lt;in...
  • 基数排序C++版)

    万次阅读 多人点赞 2015-08-16 15:54:42
    void radixsort(int data[], int n) //基数排序 { int d = maxbit(data, n); int tmp[n]; int count[10]; //计数器 int i, j, k; int radix = 1; for(i = 1; i ; i++) //进行d次排序 { for(j = 0; j ; j++) ...
  • 基数排序(C++实现)

    2020-12-24 08:59:24
    基数排序 #include <iostream> #include <list> using namespace std; int maxdigit(int data[], int n) { int d = 1; // 计位器: 1 1位数 2 两位数 int p = 10; // 倍数 // 求数组中最高位的的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,360
精华内容 4,544
关键字:

基数排序c++

c++ 订阅