文档章节

RadixSort -- 基数排序

gackey
 gackey
发布于 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] + "");
        }
    }
}

 

本文转载自:

共有 人打赏支持
gackey
粉丝 3
博文 61
码字总数 10503
作品 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
QuickSort快排详细解释

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

franos
2016/03/24
53
0
几种排序算法的JAVA语言实现

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

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

没有更多内容

加载失败,请刷新页面

加载更多

在Debian 9系统上安装Mysql数据库的方法教程

前言 看到题目大家应都会想,在 Debian 9 上安装 Mysql?那不是很简单的事儿吗?直接 sudo apt install mysql-server 不就行了吗? 没想到遇到了几个之前没遇到的问题,耽误了不少时间。 原来...

临江仙卜算子
42分钟前
4
1
从web实时通信讲H5 WebSocket

通常我们打开一个浏览器访问网页时,都会向页面所在的服务器发送一个HTTP请求,然后web服务器确认请求并向浏览器做出响应。简单的说,就是一个请求对应的一个响应。然而这种方法对许多的应用...

Code辉
56分钟前
3
0
Sharding-Sphere自动化执行引擎

Q: 什么叫"自动化执行引擎"? A: 一条SQL的生命周期是:从客户端发起、经过Sharding-Sphere处理、再到底层数据库执行消化。而在Sharding-Sphere里过程则是:SQL解析-->SQL优化-->SQL路由-->...

xiaomin0322
59分钟前
2
0
单模块中ReentrantLock的使用

背景 在单模块应用中,对同一个请求,需要进行同步。注意ReentrantLock的使用场景: 同一个线程中 同一个请求 RestController @RestControllerpublic class Controller {private final Re...

亚林瓜子
今天
2
0
Linux 4.1内核热补丁成功实践

好久不见的干货重现江湖!今日的内容是基于UCloud运维同学反馈的个别宿主机上存在进程CPU峰值使用率异常现象问题进行的相关阐述。本文详细介绍了该问题的完整分析思路和用热补丁的方式成功解...

UCloudTech
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部