文档章节

RadixSort -- 基数排序

ninjaFrog
 ninjaFrog
发布于 2017/09/08 00:33
字数 548
阅读 3
收藏 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 = new int[10][number.length]; // 数组的第一维表示可能的余数0-9
        int[] order = new int[10]; // 数组order[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] + " ");
        }
    }
}

 

© 著作权归作者所有

共有 人打赏支持
ninjaFrog
粉丝 3
博文 66
码字总数 17262
作品 0
昌平
程序员
私信 提问
android ndk 基数排序

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

貌似高手
2012/07/09
0
0
数据结构基础(15) --基数排序

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

翡青
2015/01/11
0
0
QuickSort快排详细解释

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

franos
2016/03/24
53
0
常用的内部排序方法-非比较排序

这篇文章中我们来探讨一下常用的非比较排序算法:计数排序,基数排序,桶排序。在一定条件下,它们的时间复杂度可以达到O(n)。   这里我们用到的唯一数据结构就是数组,当然我们也可以利用...

亮亮-AC米兰
2017/01/22
0
0
几种排序算法的JAVA语言实现

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

奔跑的蛮牛
2013/12/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Flink 幕后之内存管理

Flink 幕后之内存管理 引言 目前很多大数据处理框架,例如Hadoop、Spark、Storm、Flink等。它们都基于JVM语言开发(java or scala),运行在JVM上。为了加速合并或者排序(基于磁盘的方式通常...

moyiguke
17分钟前
2
0
风起云涌,看云计算如何赋能媒体行业?

在媒体行业的转型升级中,云计算的出现多维度促进了媒体融合,打破传统媒体行业与新媒体的界限和竞争格局,在媒体素材管理、移动端功能演进的过程中扮演着重要角色,颠覆了传统媒体新闻采编、...

七牛云
20分钟前
0
0
Mybatis开发遇到问题汇总

mybatis 中![CDATA[...]] 在今天使用Mybatis的xml文件中写sql语句时写入了一些特殊字符 如 < > & 等,但解析xml文件的时候会被转义,事实上并不希望它被转义,可以使用<![CDATA[ ]]>. 这是XML...

wangwei2134
28分钟前
0
0
参数验证 @Validated 和 @Valid 的区别

来源:blog.csdn.net/qq_27680317/article/details/79970590 整编:Java技术栈(公众号ID:javastack) Spring Validation验证框架对参数的验证机制提供了@Validated(Spring's JSR-303 规范......

Java技术栈
30分钟前
0
0
JS实现继承的几种方式

前言 JS作为面向对象的弱类型语言,继承也是其非常强大的特性之一。那么如何在JS中实现继承呢?让我们拭目以待。 JS继承的实现方式 既然要实现继承,那么首先我们得有一个父类,代码如下: ...

不负好时光
34分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部