文档章节

RadixSort -- 基数排序

garkey
 garkey
发布于 2017/09/08 00:33
字数 478
阅读 2
收藏 0
点赞 0
评论 0

 基数排序属于“分配式排序”(distribution sort),又称“桶排序”(bucket sort)或bin sort ,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数。

LSD : "最低位优先" 法

MSD : "最高位优先" 法

/*

待排序数组[62,14,59,88,16]简单点五个数字

分配10个桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样

|  0  |  0  | 62 |  0  | 14 |  0  | 16 |  0  | 88 | 59 |

|  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |桶编号

将桶里的数字顺序取出来,

输出结果:[62,14,16,88,59]

再次入桶,不过这次以十位数的数字为准,进入相应的桶,变成下边这样:

由于前边做了个位数的排序,所以当十位数相等时,个位数字是由小到大的顺序入桶的,就是说,入完桶还是有序

|  0  | 14,16 |  0  |  0  |  0  | 59 | 62  | 0  | 88 |  0  |

|  0  |    1     |  2  |  3  |  4  |  5  |  6   |  7 |  8  |  9  |桶编号

因为没有大过100的数字,没有百位数,所以到这排序完毕,顺序取出即可

最后输出结果:[14,16,59,62,88]

*/

LSD代码如下:

public class RadixSort{
    public static void sort(int[] number, int d) { //d表示最大的数有多少位
        int k = 0;
        int n = 1;
        int m = 1; //控制键值排序依据在哪一位
        int[][] temp = newint[10][number.length]; //数组的第一维表示可能的余数0-9
        int[] order = newint[10]; //数组orderp[i]用来表示该位是i的数的个数
        while(m <= d)
        {
            for(int i = 0; i < number.length; i++)
            {
                int lsd = ((number[i] / n) % 10);
                temp[lsd][order[lsd]] = number[i];
                order[lsd]++;
            }
            for(int i = 0; i < 10; i++)
            {
                if(order[i] != 0)
                    for(int j = 0; j < order[i]; j++)
                    {
                        number[k] = temp[i][j];
                        k++;
                    }
                order[i] = 0;
            }
            n *= 10;
            k = 0;
            m++;
        }
    }

    public static void main(String[] args){
        int[] data = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
        RadixSort.sort(data, 3);
        for(int i = 0; i < data.length; i++)
        {
            System.out.print(data[i] + "");
        }
    }
}

 

本文转载自:

共有 人打赏支持
garkey
粉丝 3
博文 58
码字总数 8942
作品 0
朝阳
程序员
android ndk 基数排序

由于工作需要需要了解一下android的ndk开发,就做了一个简单的例子。 环境jdk1.6,ndk=android-ndk-r8-windows,eclips3.7,androidsdk=10 功能:android的调用一个c99写的基数排序方法 工程结构...

貌似高手
2012/07/09
0
0
Visual Studio 11开发指南(19)C++11更新-并行模式库和代理库

Visual Studio 11,具备并行模式库和代理库、 更轻松地开发多核处理器上运行的并行代码。 这些库的主要范例是根据任务 和并发运行库,自定义的调度程序 进行处理的。 到目前为止,处理任务的...

junwong
2012/03/09
0
0
数据结构基础(15) --基数排序

基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 实现多关键字排序通常有两种作法: 最低位优先法(LSD) 先对K[0]{基数的最低位}进行排序,并按 K(0) 的不同...

翡青
2015/01/11
0
0
几种排序算法的JAVA语言实现

1、选择排序最差时间复杂度О(n²)最优时间复杂度О(n²)平均时间复杂度О(n²)最差空间复杂度О(n) total, O(1) auxiliary选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理...

奔跑的蛮牛
2013/12/22
0
0
QuickSort快排详细解释

快速排序在最差排序速度,平均排序速度,上都十分优秀,经过简单大数据数组测试,快速排序至少比冒泡排序(这一类复杂度为log(n^2)的排序法)快5倍,废话少说,直接上代码上解释 以下是C++代码,...

franos
2016/03/24
53
0
十大经典算法总结(Javascript描述)

前言 读者自行尝试可以想看源码戳这,博主在github建了个库,读者可以Clone下来本地尝试。此博文配合源码体验更棒哦~~~ 个人博客:Damonare的个人博客 原文地址:十大经典算法总结 - 这世界上...

Damonare
2016/09/17
1K
4
数据结构-基数排序(桶排序)

基数排序和计数排序都属于“非比较排序”,有关计数排序可查看http://blog.csdn.net/sssssuuuuu666/article/details/78677302。 基数排序介绍: 基数排序(radix sort)属于“分配式排序”(...

sssssuuuuu666
2017/12/15
0
0
内部排序方法

1、分类 按平均时间将排序分为四类: a、平方阶(O(n2))排序 一般称为简单排序,例如直接插入、直接选择和冒泡排序; b、线性对数阶(O(nlgn))排序 如快速、堆和归并排序; c、O(n1+£)阶排序 ...

野渡书生
2016/05/03
14
0
各种排序算法及其java程序实现

各种排序算法:冒择路(入)兮(稀)快归堆,桶式排序,基数排序 冒泡排序,选择排序,插入排序,稀尔排序,快速排序,归并排序,堆排序,桶式排序,基数排序 一、冒泡排序(BubbleSort) 1. 基本思...

长平狐
2012/09/03
7.8K
0
九大排序算法稳定性

In-place sort(不占用额外内存或占用常数的内存):插入排序、选择排序、冒泡排序、堆排序、快速排序。 Out-place sort:归并排序、计数排序、基数排序、桶排序。 stable sort:插入排序、冒...

曾劲松
2016/04/11
102
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

告警系统主脚本、告警系统配置文件、告警系统监控项目

告警系统主脚本 为方便需要,所有的shell脚本放到 /usr/local/sbin/ 目录下 切换到 /usr/local/sbin/ 目录下,创建告警系统脚本 #!/bin/bash#Written by aming.# 是否发送邮件的开关(1表...

Zhouliang6
3分钟前
1
0
不要再问我跨域的问题了

原文链接:web.jobbole.com 【RTC实时互联网大会 限时免费 马上报名】www.bagevent.com 写下这篇文章后我想,要不以后就把这种基础的常见知识都归到这个“不要再问我XX的问题”,形成一系列内...

阿K1225
5分钟前
0
0
Tomcat配置虚拟路径

<?xml version="1.0" encoding="UTF-8"?> <Context docBase="/data/dispute_https/headPortrait/" path="/headPortrait" reloadable="true"/> <!-- 该文件名为headPortrait.xml,放在${tomca......

Helios51
6分钟前
0
0
开源PaaS Rainbond 3.6.1 Released

本次3.6.1版本更新,重点修复了3.6.0版本部分情况下会出现的BUG,同时改进了内部市场、参数验证、历史消息等功能,详细更新记录如下—— 3.6.1 功能改进 云帮初次使用跳转至注册页面 消息添加...

好雨云帮
7分钟前
0
0
Unsupported major.minor version 52.0

执行代码的jdk版本 低于 编译的jdk版本 其中52.0 对应的就是 jdk1.8版本。

@林文龙
7分钟前
0
0
聊聊spring cloud的AbstractLoadBalancingClient

序 本文主要研究一下spring cloud的AbstractLoadBalancingClient AbstractLoadBalancingClient spring-cloud-netflix-ribbon-2.0.0.RELEASE-sources.jar!/org/springframework/cloud/netfli......

go4it
8分钟前
0
0
博客改版通知

先上博客地址 --> http://metaphors.name 最近将博客从 Jekyll 迁到了 Hexo,所以简书、开源中国、博客园、CSDN文章中的的部分图片丢了,原文链接也不可用了,不过没关系,原文链接都会转到博...

Metaphors
8分钟前
0
0
vue基础知识练习

一、Hello World <div id="itany">{{msg}} <!-- 两对大括号{{}}称为模板,用来进行数据的绑定显示在页面中 --> </div><script src="js/vue.js"></script><script>var vm=new Vue({......

一个yuanbeth
12分钟前
0
0
spring @Transactional注解参数详解

原文:事物注解方式: @Transactional 当标于类前时, 标示类中所有方法都进行事物处理 , 例子: 1 @Transactional public class TestServiceBean implements TestService {} 当类中某些方法不需...

binhu
15分钟前
0
0
CORS 跨域实践

本文首发于个人微信公众号《andyqian》,期待你的关注~ 前言 系统通常都是由单体应用逐渐演化而来,演化成为前后端分离的分布式应用。在享受分布式系统带来的诸多好处之时,随之而来的也有不...

andyqian
22分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部