基数排序 柔情只为你懂 2022-05-12 02:54 272阅读 0赞 #### 写在前面 #### > 计数排序,基数排序 #### 总结 #### 计数排序是非基于比较的排序方式,和一般基于比较的排序不同。 基于比较的排序的算法的平均复杂度的下界也是o(nlgn)。但是对于某些特定情况的输入来说可以使用非比较排序算法使得复杂度降低。 如果输入的数据是非负整型值,而且元素的最大值是一个有限的值K,那么在K不是特别大的情况下是可以得到o(n)的排序算法的。当数据长度n和K在一个数量级的情况下,计数排序就能够达到效果,当k为n的多项式级别基数排序可以达到效果。 #### 基数排序实现 #### #include <iostream> #include <vector> using namespace std; /** * 基数排序。 * 采用的基数是10,那么每个桶的范围就是0,1,2,3,4,5,6.。。9 * 对每个元素按照位从低到高做计数排序 时间复杂度为o(n+9) * 一共需要做的趟数是最大的元素的的位数k * 总时间复杂度为O(k*n)当最大值为n的多项式级别是时k为常数级别。 * 总体时间复杂度为o(n) */ int getDigitNumber(int x) { int n = 0; while(x>0) { x /= 10; ++n; } return n; } int getD(int x,int d) { int val = 0; while(d) { val = x%10; x /= 10; --d; } return val; } /* 计数排序: 1.开辟一个长度为基数b的桶 2.开辟一个临时的数组 3.对于每一个元素的第d位在桶中计数 3.将桶当中的值进一步修改为该值应该出现在的最大位置的下一个 4.从后往前遍历元素放置每一个元素到临时数组的指定的位置。 5.将临时数组拷贝回原始数组。 */ void count_sort(vector<int>& vec,int d) { vector<int> table(10,0); vector<int> tempVec(vec.size(),0); for(int i=0;i<vec.size();++i) table[getD(vec[i],d)%10] += 1; for(int i=1;i<10;++i) table[i] += table[i-1]; for(int i=vec.size()-1;i>=0;--i) { int j = getD(vec[i],d)%10; tempVec[table[j]-1] = vec[i]; table[j] -= 1; } for(int i=0;i<vec.size();++i) vec[i] = tempVec[i]; return; } /* 基数排序: 1.遍历数组找到最大值 2.获取该最大值的位数 3.从低位开始迭代计数排序 */ void redix_sort(vector<int>& vec) { int n = vec.size(); if(n<=1) return; int m = 0; for(int i=0;i<n;++i) { m = max(vec[i],m); } int d = getDigitNumber(m); for(int i=1;i<=d;++i) count_sort(vec,i); return; } /* 测试代码 */ int main() { vector<int> vec{ 123,4,55,78,9,223,4,12,44,345,1234,1222}; redix_sort(vec); for(auto each:vec) cout << each << endl; return 0; }
相关 基数排序 基数排序与本系列前面讲解的七种排序方法都不同,它不需要比较关键字的大小。 它是根据关键字中各位的值,通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。 不 以你之姓@/ 2022年08月21日 05:35/ 0 赞/ 198 阅读
相关 基数排序 基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。比较官方地说,基数排序是一种基于多关键字的排序。 基 蔚落/ 2022年06月15日 06:11/ 0 赞/ 221 阅读
相关 基数排序 对于一个int数组,请编写一个基数排序算法,对数组元素排序。 给定一个int数组A及数组的大小n,请返回排序后的数组。保证元素均小于等于2000。 测试样例: 分手后的思念是犯贱/ 2022年06月09日 01:36/ 0 赞/ 215 阅读
相关 基数排序 基数排序 算法描述: 分别比较个位,十位,百位,千位等数据的大小,比较方法依赖其他排序方法,可以计数排序。 时间复杂度:O(d(r+n)) 空间复 分手后的思念是犯贱/ 2022年05月28日 00:26/ 0 赞/ 59 阅读
相关 基数排序 写在前面 > 计数排序,基数排序 总结 计数排序是非基于比较的排序方式,和一般基于比较的排序不同。 基于比较的排序的算法的平均复杂度的下界也是o(nlgn)。 柔情只为你懂/ 2022年05月12日 02:54/ 0 赞/ 273 阅读
相关 基数排序 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。 客官°小女子只卖身不卖艺/ 2022年01月29日 02:01/ 0 赞/ 285 阅读
相关 基数排序 package com.sort; / @Auther: 大哥的叔 @Date: 2019/8/8 13:06 @ àì夳堔傛蜴生んèń/ 2021年11月05日 18:12/ 0 赞/ 311 阅读
相关 基数排序 在箱子排序中,尽管时间复制度仅仅有(n),但假设其箱子序列较大的话将会导致程序的空间复杂度较大,所以对于对于属性值跨度比較大的序列能够採用基数排序法。 概述:详细的做法 痛定思痛。/ 2021年09月19日 10:12/ 0 赞/ 387 阅读
相关 基数排序 在介绍基数排序前,我们先简单介绍下桶排序:例如有10个桶,我们给分边编号1——10,然后寻找其中装有水的桶。 ![70][] 我们可以显而易见,其中装有水的桶编号是 清疚/ 2021年09月15日 20:52/ 0 赞/ 397 阅读
还没有评论,来说两句吧...