1.基数排序
基数排序的思想是针对整数的每一位进行排序,它是一种稳定的排序,从个位开始比较,小的再前面,大的排在后面,然后顺次取出,对取出后的数据组针对下一位再进行排序,一直排到位数最多的那一位排完为止!
当桶排序的输入符合均匀分布时,可以期待线性期望时间运行,它的时间复杂度大概为o(n*m);n代表数组长度,m代表最长位的位数。
但桶排序的缺点是耗费空间比较大,而且它并不能排序小数,不过可以先将小数转换为整数,再排序,以及负数,负数要分两部分排,首先是纯正数A那一块先排,然后负数为一块B化为正数再排,然后转换为负数颠倒,然后再加上原先的正数A那一堆组合起来!
示例代码如下:
#include <iostream> #include<vector> using namespace std; vector< vector<int> > myVector;//二维 //后续处理 //取出排序后的数 void follow_Slove(int* A) { int vert = 0; for ( int i=0; i< myVector.size(); i++) { for ( int j=0; j< myVector[i].size(); j++) { A[vert] = myVector[i][j]; vert++; } myVector[i].clear();//移除所有元素 } } /*基数排序,又名桶排序 A:待排数组 len:数组长度 bitLen:最长整数的位数 默认采用10进制数 */ void bucket_Sort(int* A,int len,int bitLen,int scale) { //基于每个数的个位,十位,百位,分别每次排序 int baseValue = 10;//为了求余取出各位数字 int vert; myVector.resize(scale); //每一位 for (int i=0;i<bitLen;i++) { //每一个数 for ( int j=0;j < len;j++) { //注意这里取每一位数的方法 vert = A[j] % baseValue;//这是得到余数 vert = vert / (baseValue/10) ; //这才取到每一位上的数 myVector[ vert ].push_back(A[j]); } //将这一遍的排序后的顺序从vector中取出并保存到原数组A,再进行下一次评价 //以及清空vector,以便下次排序 follow_Slove(A); baseValue = baseValue * 10; //改变求余 } } //计算整数的最长位是多少 void cal_bitLen(int* A,int len,int& bitLen) { int max = -1; //保存最长位 int temp; int count = 1; for ( int i=0; i < len ; i++) { temp = A[i]; count = 0; while ( temp) { temp = temp/10; count++; } if ( count > max) max = count; } bitLen = max ; } int main(void) { int A[6] = {1111,22,22,224,50,0}; int bitLen; cal_bitLen(A,6,bitLen); bucket_Sort(A,6,bitLen,10); for (int i=0;i<6;i++) { cout << A[i]<<" "; } cout<<endl; return 0; }
发表评论
-
QQ中杂七杂八的调用点
2016-03-28 20:52 0QQ中的API调用太多了,在这里做一个记录,方便以 ... -
c++面试题
2013-10-08 21:55 2911. 如何设计一个不能被继承的类 http://sn ... -
各类公司2014笔试题
2013-09-17 09:33 657美团: http://www.itmian4.com/f ... -
面试题汇总
2013-08-30 00:53 7441.题目:给定数组A,大小为n,数组元素为0到n-1的数字 ... -
非递归、仅用一个栈、不加标记数组实现二叉树的后序遍历算法
2013-08-18 23:55 0http://www.cnblogs.com/fin ... -
球称重问题
2013-07-28 22:47 0一般的问题是,如果明确次品球是重或轻,可以直接利用公式 ... -
随机概率相关面试题详解
2013-05-15 10:46 01. 已知有个rand7()的函数,返回1到7随机 ... -
c++---高级技术
2015-01-04 00:13 7401. 异常对象没有专门的头文件。 2.不应该 ... -
深度探索c++对象模型
2013-03-25 16:57 0这本书大概看了 ... -
c++ Primer 学习笔记
2013-03-20 14:28 01.Protected 成员 (1)像private成 ... -
字符串的相关标准函数库重写
2013-03-11 09:59 0#include <iostream> #i ... -
csdn------屌丝们的欢乐算法题
2013-03-08 21:34 01. 1 2 3 ... -
贪心算法---基础篇
2012-08-26 13:20 0理论部分 贪 ... -
计算几何-----判断一个点是否在多边形内
2012-08-20 15:01 0如何判断点在多 ... -
大整数相关运算
2012-08-20 13:52 0既然这是我的暑假任务,那么不管怎样一定要按计划完成了! ... -
编程之美---寻找发帖水王(含扩展问题)
2012-08-19 10:11 0题目:Tango是微软亚洲 ... -
编程之美-----2.21只考加法的面试题
2012-08-12 19:59 0http://www.cnblogs.com/flyinghe ... -
前序+中序==>后序 && 后序+中序==>前序
2012-08-12 09:49 0一. 前序 + 中序 -> 后序 分析: ... -
DE算法学习
2012-08-07 12:38 0DE(差分演化算法) 理论: 这部分内容直接参 ... -
扩展欧几里得与模线性方程
2012-02-05 23:47 0对任意的非负整数a ...
相关推荐
经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - ...
C语言实现常见排序算法。编译环境:VS2010。 包括: 冒泡排序 快速排序 直接插入排序 Shell排序 直接选择排序 堆排序 归并排序(递归和非递归两种) 桶式排序 基数排序:顺序和静态队列两种方法 索引排序(采用简单...
Java排序算法:插入,冒泡,选择,Shell,快速排序,归并排序,堆排序,桶式排序,基数排序
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
基数排序/桶排序 *统计将数组中的数字分配到桶中后,各个桶中的数字个数 *数组中每个数的每一位数根据大小分配到对应大小为0~9的桶 *将各个桶中的数字个数,转化成各个桶中最后一个数字的下标索引
在这份文档中,我用C语言实现了排序算法的多种方法,包括插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、桶排序和基数排序。这些算法可以帮助我们对数据进行有效的排序和整理,以便更好地处理和分析...
本项目用C++中实现了冒泡排序、插入排序、堆排序、希尔排序、归并排序、基数排序、选择排序、桶排序、快速排序
数据结构之排序算法 包含目前所有排序方法: 1 快速排序 2 冒泡排序 3 堆排序 4 希尔排序 5 直接插入排序 6 直接选择排序 7 基数排序 8 箱、桶排序 9 归并排序
基数排序法又称「桶子法」(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些「桶」中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),...
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
算法导论之基数排序,桶排序。基数排序是利用在各个位上进行计数排序,是一种线性排序
数据结构与算法-Python语言案例实现十大经典排序算法一、 引言1.问题需求2.... 桶排序(Bucket Sort)10. 基数排序(Radix Sort)三、算法总结 十大经典排序算法 一、 引言 授人以鱼不如授人以渔~ 实践是检
快速排序
基数排序是一种非比较型整数排序算法,它通过按数字的各个位数进行排序来实现整体序列的有序化。该算法首先确定待排序序列中最大数的位数,然后从最低位(个位)开始,依次对每一位进行排序。在排序过程中,通过创建...
4. 线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。 关于稳定性: 稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。 不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。
该工具包含有Java一些比较常见的排序算法和...排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数排序(桶排序) 查找算法包括:线性查找、二分查找、插值查询、斐波那契(黄金分割法)、
十大常用排序算法整理及C++实现。包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序,并对简要说明了算法步骤及相应的算法复杂度。