基数排序

假设对0~10^6-1的1000个整数进行排序,使用基数排序r=10^6的排序方法相当于直接对数使用箱子排序。对箱子的初始化需要10^6个执行步,节点分配需要1000个执行步,收集箱子节点需要10^6个执行步,总的执行步数为2001000。 使用基数r=1000的排序方法,其过程如下: (1)采用每个数的最低3位数字进行排序,令range=1000; (2)对(1)的结果按倒数次3位(即倒数第4到第6位)数字进行排序。 上述每次排序都需要3000个执行步,因此总共需要6000步。若使用基数为r=100的排序方法,则需要三次箱子排序,每次针对两位数字。每次箱子排序需要1200个执行步,总的执行步数为3600.如果使用基数为r=10的排序方法,则要进行6次箱子排序,每次针对一位数字,总的执行步骤数为6*(10+1000+10)=6120.对于本例,基数r=100的排序效率最高。 把数分解为数字需要除法和取模操作。如果用基数10来分解,那么从最低位到最高位的数字分解式为: x%10; (x%100)/10; (x%1000)/100; …… 若r=100,则相应的数字分解式为: x%100; (x%10000)/100; (x%1000000)/10000; …… 对于一般的基数r,相应的分解式为: x%r; (x%r^2)/r; (x%r^3)/r^2; …… 当使用基数r=n对0~n^c-1范围内的n个整数进行分解时,每个数可以分解出c个数字。因此,对n个数,可以用c次range=n个箱子排序。因为c是一个常量,所以整个排序时间为O(cn)=O(n)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Albert陈凯

理解Scala的函数式风格:从var到val的转变

Scala允许你用指令式风格编程,但是鼓励你采用一种更函数式的风格。如果你是从指令式的背景转到Scala来的——例如,如果你是Java程序员——那么学习Scal...

23830
来自专栏软件开发 -- 分享 互助 成长

简单工厂模式

一、简单工厂模式的相关概念: 1、定义:简单工厂模式是属于创建型模式,又叫做静态工厂方法(Static Factory Method)模式。 其核心思想就是有一...

19090
来自专栏木制robot技术杂谈

谈一谈Python中str()和repr()的区别

前言 在学习BeautifulSoup文档的时候发现了一个以前不常见的Python内建函数repr(),带着好奇对这个内建函数进行了一番搜索和学习。 总结 s...

36840
来自专栏申龙斌的程序人生

零基础学编程028:面向对象编程OOP

在《零基础学编程021:获取股票实时行情数据》一节中,我们想获取6支股票的行情数据,在《零基础学编程022:函数的世界》里我们能够把重复性的代码封装为一个函数p...

31760
来自专栏python读书笔记

《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

21660
来自专栏Android机动车

设计模式——抽象工厂模式

● 为创建一组相关或依赖的对象提供一个接口,而无需指定他们的具体类型。是工厂方法模式的升级版。

7910
来自专栏magicsoar

Effective Modern C++翻译(6)-条款5:auto比显示的类型声明要更好

    在概念上说,auto关键字和它看起来一样简单,但是事实上,它要更微妙一些的。使用auto会让你在声明变量时省略掉类型,同时也会防止了手动类型声明带来的正...

206100
来自专栏老九学堂

零基础学Java第三讲变量

如何掌握了变量这个语法?看看微视频中对应的知识点的讲解。 别走开,下面有干货哦! 1了解什么是变量?变量如何使用? 2会使用常用的数据类型 任何编程语言的语...

30450
来自专栏Crossin的编程教室

【Python 第55课】 正则表达式(1)

今天来挖个新坑,讲讲正则表达式。 什么是正则表达式?在回答这个问题之前,先来看看为什么要有正则表达式。 在编程处理文本的过程中,经常会需要按照某种规则去查找一些...

28670
来自专栏前端说吧

JS-几大排序算法(更新中...)

46750

扫码关注云+社区

领取腾讯云代金券