文档章节

RadixSort -- 基数排序

NinjaFrog
 NinjaFrog
发布于 2017/09/08 00:33
字数 478
阅读 2
收藏 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] + "");
        }
    }
}

 

本文转载自:

共有 人打赏支持
上一篇: UML类图
NinjaFrog
粉丝 3
博文 64
码字总数 11574
作品 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
几种排序算法的JAVA语言实现

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

奔跑的蛮牛
2013/12/22
0
0
数据结构基础(15) --基数排序

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

翡青
2015/01/11
0
0
十大经典算法总结(Javascript描述)

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

Damonare
2016/09/17
1K
4

没有更多内容

加载失败,请刷新页面

加载更多

node上的redis调用优化示例

Node.js读写数据到influxDB,目前已经有一个库node-influx, 这个库功能非常强大,但是我个人使用这个库的时候,遇到无法解决的问题。 使用curl都可以写数据到influxDB,但是用node-influx总是...

前端攻城老湿
11分钟前
1
0
The setting logImpl is not known

问题: org.apache.ibatis.builder.BuilderException: The setting logImpl is not known. Make sure you spelled it correctly (case sensitive). MyBatis 3.1.1 -jar还没有 logImpl 这个设......

晨猫
23分钟前
1
0
eslint一些规则

一、指定js文件不使用 ESLint 语法检查 1.整个文件范围内禁止规则出现警告 将/* eslint-disable */放置于文件最顶部 /* eslint-disable */alert('foo'); 2.在文件中临时禁止规则出现警告 ...

xiaoge2016
23分钟前
1
0
mac终端常用命令

ls ls,list的简写,列出目录的内容。 -a:显示隐藏文件 -l:以列表方式显示文件信息 -h:配合-l,显示更人性化 配合通配符使用 ls *.txt:显示所有以.txt结尾的文件 ls ?.txt:显示‘任意字符.tx...

xiaobai1315
25分钟前
1
0
java命令行读取配置,和加载jar的方式

--spring.profiles.active=t2,t3,xextest --spring.profiles.include=quartz-jp-Djava.ext.dirs=libs-Dspring.config.location=/data/apps/DBconfig -cp  "config/*"  start.sh......

经常把天聊死的胖子
36分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部