0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看技术视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

基数排序是怎么排的_基数排序详细过程

lhl545545 来源:电子发烧友网 2018-02-05 14:11 次阅读

计数排序

学习基数排序之前首先学习计数排序。

计数排序假设每个元素都是在0到k之间的一个整数。

基数排序的基本思想,对于每个元素x,如果我们知道了小于x的元素的个数,就可以确定输出数组中元素x的位置,那么直接将元素x放到输出数组中。比如有3小于x的元素,那在输出数组中,x肯定位于第4个位置。

计数排序的算法用伪代码描述为:

COUNTING-SORT(A,k)

// 初始化数组C

for i=0 to k

C[i]=0

// 统计A[j]元素出现的次数,保存到C数组中

for j=0 to A.length

C[A[j]]=C[A[j]]+1

// 统计小于等于A[j]元素的个数

for k=0 to k

C[K]=C[K-1]+C[K]

// 将A中的元素放在B中正确的位置

for i=A.length to 0

B[C[A[i]]-1]=A[i]

C[A[i]]=C[A[i]]-1

注:由于有可能有相同元素存在,所以,每次将A[i]元素放入B数组中,都要将C[A[j]]的值减一,这样当遇到下一个值等于A[j]的元素时,该元素就能放在输出数组中A[j]的前面。

计数排序的详细过程如下

基数排序是怎么排的_基数排序详细过程

计数排序的关键代码如下

public int[] countSort(int a[], int k) {

int[] b = new int[a.length];

int[] c = new int[k];

for (int i = 0; i

c[i] = 0;

}

for (int i = 0; i

c[a[i]] += 1;

}

for (int i = 0; i

if (i != 0) {

c[i] += c[i - 1];

}

}

for (int i = a.length - 1; i >= 0; i--) {

b[c[a[i]] - 1] = a[i];

c[a[i]] = c[a[i]] - 1;

}

return b;

}

计数排序的性能

很容易得到计数排序的时间复杂度为:T(n)=O(k+n),因此当k小于等于n,也就是当k=O(n),k和n同阶时,采用计数排序的时间复杂度为T(n)=O(n)

同时,计数排序也是一种稳定的排序算法。

基数排序

基数排序最初是用在打孔卡片制表机上的一种排序算法,由Herman Hollerith发明,也就是IBM的创始人。

基数排序从最低为开始来排序的,从低位到高位,按位排序,按位排序必须是稳定的。

基数排序的详细过程

基数排序是怎么排的_基数排序详细过程

基数排序算法描述

RADIX-SORT(A,d)

for i=1 to d

use a stable sort to sort arrat A on digit i

在这里我们选择计数排序。考虑常规情况,对[0.。.9]之间的数排序,k=10,且一般有k<

基数排序的关键代码,这里以数组排序时按照十进制每位进行比较。

/**

* 基数排序

* @param result 最终已排序的数组,共用一个节省空间

* @param maxLen 待排序的数组中最大的位数

*/

public static void radixSort(int[] a,int[] result, int maxLen) {

int flag = 1;

// 保存每轮要排序的位对应数组a的值

int [] digitArr = new int[a.length];

for(int i=0; i

// 共比较的轮数

flag *= 10;

// b数组中对应的装着a数组中每位的数,第一轮装着各位,第二轮装着十位数。。.

for (int j = 0; j < digitArr.length; j++) {

digitArr[j]=a[j]%flag;

digitArr[j]=digitArr[j]/(flag/10);

}

countSort(a, digitArr,result,10);

// 每一轮计数排序完后刷新下一轮要排序的数组

System.arraycopy(result, 0, a, 0,result.length);

}

}

调用计数排序的函数

/**

* 计数排序 :对数组a中的元素按某些位排序

* @param tmp 要参与排序的当前位的值保存在tmp中

* @param result 每次计数排序后的新的数组顺序

*/

public static void countSort(int a[], int tmp[], int result[], int k) {

int[] c = new int[k];

for (int i = 0; i < c.length; i++) {

c[i] = 0;

}

for (int i = 0; i

c[tmp[i]] += 1;

}

for (int i = 0; i < c.length; i++) {

if (i != 0) {

c[i] += c[i - 1];

}

}

for (int i = tmp.length - 1; i >= 0; i--) {

// 和计数排序唯一的差别在于赋值的时候用真实的数据

result[c[tmp[i]] - 1] = a[i];

c[tmp[i]] = c[tmp[i]] - 1;

}

}

基数排序的性能

如果基数排序使用的稳定排序算法的时间复杂度为O(n+k),那么基数排序的时间复杂度为T(n)=O(d(n+k))

很容易理解要循环d轮,每轮耗时为O(n+k),于是总的耗时为O(d(n+k))

在此基础上,从2^r进制来看,此时k为2^r,并且一个b位数要比较b/r轮。于是我们得到T(n)=O((b/r)(n+2^r))

对上式求导可得其最小值。此时r=lgn,此时T(n)=O((b/lgn)n),如果再取b=lgn,这时就能达到最少的运行时间,时间复杂度为T(n)=O(n)

基数排序也是稳定的排序算法

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
收藏 人收藏

    评论

    相关推荐

    在TMS320C62x上实现的扩展精度基数-4快速傅里叶变换

    电子发烧友网站提供《在TMS320C62x上实现的扩展精度基数-4快速傅里叶变换.pdf》资料免费下载
    发表于 10-28 10:03 0次下载
    在TMS320C62x上实现的扩展精度<b class='flag-5'>基数</b>-4快速傅里叶变换

    时间复杂度为 O(n^2) 的排序算法

    作者:京东保险 王奕龙 对于小规模数据,我们可以选用时间复杂度为 O(n2) 的排序算法。因为时间复杂度并不代表实际代码的执行时间,它省去了低阶、系数和常数,仅代表的增长趋势,所以在小规模数据情况下
    的头像 发表于 10-19 16:31 1150次阅读
    时间复杂度为 O(n^2) 的<b class='flag-5'>排序</b>算法

    TPS54120排序和跟踪

    电子发烧友网站提供《TPS54120排序和跟踪.pdf》资料免费下载
    发表于 10-10 10:54 0次下载
    TPS54120<b class='flag-5'>排序</b>和跟踪

    OPSL 优势4:良好的可靠性 - 庞大的安装基数

    光泵半导体激光器 (OPSL) 是一项独有的技术,与其他连续 (CW) 固态激光器相比,它具有良好的可靠性和使用寿命。 加上 OPSL 的其他优势,这种激光器的安装量接近 100,000 万台,应用于从生命科学到灯光表演等各种要求严格的领域,这证明了其可靠性。 出色的可见光和紫外光可靠性 在过去的 50 年中,出现了几种不同的技术,为连续 (CW) 可见光和紫外光激光器的应用提供了支持。 首先是离子激光器,然后是灯泵浦固态、半导体泵浦固态 (DPSS)、激光半导体
    的头像 发表于 07-11 06:37 304次阅读
    OPSL 优势4:良好的可靠性 - 庞大的安装<b class='flag-5'>基数</b>

    手把手教你排序算法怎么写

    今天以直接插入排序算法,给大家分享一下排序算法的实现思路,主要包含以下部分内容:插入排序介绍插入排序算法实现手把手教你排序算法怎么写在添加新
    的头像 发表于 06-04 08:03 687次阅读
    手把手教你<b class='flag-5'>排序</b>算法怎么写

    具有先进排序和输出裕度的中输入同步降压控制器TPS40101数据表

    电子发烧友网站提供《具有先进排序和输出裕度的中输入同步降压控制器TPS40101数据表.pdf》资料免费下载
    发表于 04-22 10:26 0次下载
    具有先进<b class='flag-5'>排序</b>和输出裕度的中输入同步降压控制器TPS40101数据表

    具有先进排序和输出裕度的中输入同步降压控制器TPS40100数据表

    电子发烧友网站提供《具有先进排序和输出裕度的中输入同步降压控制器TPS40100数据表.pdf》资料免费下载
    发表于 04-17 10:59 0次下载
    具有先进<b class='flag-5'>排序</b>和输出裕度的中输入同步降压控制器TPS40100数据表

    3-A、3.3/5V输入、可调开关稳压器,具有自动跟踪TM排序功能PTH04000W数据表

    电子发烧友网站提供《3-A、3.3/5V输入、可调开关稳压器,具有自动跟踪TM排序功能PTH04000W数据表.pdf》资料免费下载
    发表于 04-17 09:32 0次下载
    3-A、3.3/5V输入、可调开关稳压器,具有自动跟踪TM<b class='flag-5'>排序</b>功能PTH04000W数据表

    Linux的sort命令介绍

    1.命令简介以行为单位对文本文件的内容进行排序,将结果显示在标准输出,比较原则是从行首字符向后,依次按 ASCII 码值进行比较,最后按升序输出。如果 file 参数指定多个文件,那么 sort
    发表于 04-08 07:16

    支持 ACPI 的 10 轨电源排序器和监视器UCD9090A数据表

    电子发烧友网站提供《支持 ACPI 的 10 轨电源排序器和监视器UCD9090A数据表.pdf》资料免费下载
    发表于 03-29 09:12 0次下载
    支持 ACPI 的 10 轨电源<b class='flag-5'>排序</b>器和监视器UCD9090A数据表

    用FPGA实现双调排序的方法(2)

    典型的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔
    的头像 发表于 03-21 10:28 638次阅读
    用FPGA实现双调<b class='flag-5'>排序</b>的方法(2)

    FPGA实现双调排序算法的探索与实践

    双调排序(BitonicSort)是数据独立(Data-independent)的排序算法,即比较顺序与数据无关,特别适合并行执行。在了解双调排序算法之前,我们先来看看什么是双调序列。
    发表于 03-14 09:50 645次阅读
    FPGA实现双调<b class='flag-5'>排序</b>算法的探索与实践

    想听听48和大对数光缆的排序

    48芯光缆和大对数光缆都是光缆中的一种,它们的区别在于芯数不同。48芯光缆指的是光缆中包含48根光纤,而大对数光缆则是指光缆中芯数超过了48芯。 在实际的光缆应用中,不同芯数的光缆需要进行不同的排序
    的头像 发表于 03-12 10:44 614次阅读

    PLC中常用进制之间是如何转换的?

    十进制(Decimal notation): 如1234=1*103+2*102+3*101+4*100,逢十进一,基数为10,单个数是0-9,每位的系数乘于基数(10)的N次方,N为其所处的位数。
    发表于 02-27 09:49 988次阅读
    PLC中常用进制之间是如何转换的?

    C语言实现经典排序算法概览

    冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。
    的头像 发表于 02-25 12:27 448次阅读
    C语言实现经典<b class='flag-5'>排序</b>算法概览