/** * 基数排序 * <ul> * <li>平均情况:O(d(r+n))</li> * <li>最好情况:O(d(rd+n))</li> * <li>最坏情况:O(d(r+n))</li> * <li>辅助存储:O(d(rd+n))</li> * <li>稳定</li> * <ul> * * @timestamp Mar 13, 2016 8:59:32 PM * @author smallbug */ public class RadixSort { public static void main(String[] args) { int[] data = DataUtil.getData(100000); // System.out.println(Arrays.toString(data)); long time = System.currentTimeMillis(); data = radixSort(data); // System.out.println(Arrays.toString(data)); System.out.println("speed " + (System.currentTimeMillis() - time) + " ms"); System.out.println("排序是否成功:" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否")); } private static int[] radixSort(int[] data) { int length = String.valueOf(data.length).toCharArray().length; for (int i = 1; i < length; i++) { int carve = (int) Math.pow(10, i);// 从个位开始比,然后十位,百位。。。 data = bucketSort(data, carve); } return data; } private static int[] bucketSort(int[] data, int carve) { int[] count = new int[10];// 计数数组 int[] result = new int[data.length];// 结果数组 for (int i = 0; i < data.length; i++) { count[(data[i] % carve) / (carve / 10)]++;// 建立计数表 } for (int i = 1; i < count.length; i++) { count[i] = count[i] + count[i - 1];// 格式化计数表 } for (int i = data.length - 1; i >= 0; i--) { result[--count[(data[i] % carve) / (carve / 10)]] = data[i];// 根据计数表排序 } return result; } }
相关推荐
包括了基数排序的实现代码和流程图。 先对个位数字进行统计,然后根据个位进行排序,然后对十位进行统计,然后根据十位进行排序,即可获得最终结果。 时间效率:待排序列为n个记录,10个关键码,关键码的取值范围为0...
基数排序基数排序基数排序基数排序基数排序
数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序
数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
基数排序法用链表完成使用C语言适用于刚入门的学者
基数排序过程及程序基数排序过程及程序基数排序过程及程序基数排序过程及程序
这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数排序法又称「桶子法」(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些「桶...
基数排序C语言实现
1.需求分析 ①.问题描述 给出一组数据,按照最低位优先的方法完成基数排序。多关键码排序按照从最主位关键码到最次位或从最次位到最主位关键码的顺序逐次排序。
基数排序算法 java实现 还有基数排序的原理文档
插入排序 冒泡排序 堆排序 基数排序 选择排序 快速排序的源码 java实现
排序算法很多,下面有基数排序,堆排序,希尔排序,直接插入排序的代码和思路
算法导论之基数排序,桶排序。基数排序是利用在各个位上进行计数排序,是一种线性排序
8646 基数排序 时间限制:1000MS 内存限制:1000K 提交次数:0 通过次数:0 题型: 编程题 语言: 无限制 描述 用函数实现基数排序,并输出每次分配收集后排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二...
Radix Sort (基数排序)排序算法
基数排序算法,这是分不错的算法,实现起来有点难,用静态链表实现,每次改变结点的指向,希望有用,多多指教
网上的一些基数排序都是用链表的,写了个非链表的例子
排序算法中的基数排序,更重要的是会算时间复杂度,基数排序可以说是以计数排序位基础的,只不过变成了一位一位来或者一个字节一个字节来,每位或者每个字节都过了一遍,则排序完毕。很简单的程序,在code::block IDE...
常用排序效率PK 冒泡 快排 选择排序 基数排序 希尔排序 折半插入排序 等