十种排序算法介绍(下)
发布日期:2021-10-12 02:13:35
浏览次数:2
分类:技术文章
本文共 1682 字,大约阅读时间需要 5 分钟。
出自matrix67.com
那么,有什么方法可以不用比较就能排出顺序呢?借助Hash表的思想,多数人都能想出这样一种排序算法来。 我们假设给出的数字都在一定范围中,那么我们就可以开一个范围相同的数组,记录这个数字是否出现过。由于数字有可能有重复,因此Hash表的概念需要扩展,我们需要把数组类型改成整型,用来表示每个数出现的次数。 看这样一个例子,假如我们要对数列3 1 4 1 5 9 2 6 5 3 59进行排序。由于给定数字每一个都小于10,因此我们开一个0到9的整型数组T[i],记录每一个数出现了几次。读到一个数字x,就把对应的T[x]加一。 A[]= 3, 1,4, 1, 5, 9, 2, 6, 5, 3, 5, 9 +---+---+---+---+---+---+---+---+---+---+ 数字 i: | 0 | 1 | 2 | 3 | 4 | 5 |6 | 7 | 8 | 9 | +---+---+---+---+---+---+---+---+---+---+出现次数T[i]: | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 | +---+---+---+---+---+---+---+---+---+---+ 最后,我们用一个指针从前往后扫描一遍,按照次序输出0到9,每个数出现了几次就输出几个。假如给定的数是n个大小不超过m的自然数,显然这个算法的复杂度是O(m+n)的。 我曾经以为,这就是线性时间排序了。后来我发现我错了。再后来,我发现我曾犯的错误是一个普遍的错误。很多人都以为上面的这个算法就是传说中的计数排序。问题出在哪里了?为什么它不是线性时间的排序算法?原因是,这个算法根本不是排序算法,它根本没有对原数据进行排序。 问题一:为什么说上述算法没有对数据进行排序? STOP! You should think fora while. 我们班有很多MM。和身高相差太远的MM在一起肯定很别扭,接个吻都要弯腰才行( 矮死了)。为此,我希望给我们班的MM的身高排序。我们班MM的身高,再离谱也没有超过2米的,这很适合用我们刚才的算法。我们在黑板上画一个100到200的数组,MM依次自曝身高,我负责画“正”字统计人数。统计出来了,从小到大依次为141,143, 143, 147, 152, 153,...。这算哪门子排序?就一排数字对我有什么用,我要知道的是哪个MM有多高。我们仅仅把元素的属性值从小到大列了出来,但我们没有对元素本身进行排序。也就是说,我们需要知道输出结果的每个数值对应原数据的哪一个元素。下文提到的“排序算法的稳定性”也和属性值与实际元素的区别有关。 问题二:怎样将线性时间排序后的输出结果还原为原数据中的元素? STOP! You should think fora while. 同样借助Hash表的思想,我们立即想到了类似于开散列的方法。我们用链表把属性值相同的元素串起来,挂在对应的T[i]上。每次读到一个数,在增加T[i]的同时我们把这个元素放进T[i]延伸出去的链表里。这样,输出结果时我们可以方便地获得原数据中的所有属性值为i的元素。 A[]= 3, 1,4, 1, 5, 9, 2, 6, 5, 3, 5, 9 +---+---+---+---+---+---+---+---+---+---+ 数字 i: | 0 | 1 | 2 | 3 | 4 | 5 |6 | 7 | 8 | 9 | +---+---+---+---+---+---+---+---+---+---+出现次数T[i]: | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 | +---+o--+-o-+-o-+-o-+-o-+--o+---+---+-o-+ | | | | | | | +--+ +-+ | | +-+ +---+ | | | A[1] | | | A[6] A[2] A[7] | A[3] A[5] A[8] | | |
转载地址:https://blog.csdn.net/qq_36747842/article/details/75453585 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月06日 12时51分03秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
备忘录模式
2019-04-28
命令模式
2019-04-28
命令模式的两种不同实现
2019-04-28
装饰器模式和代理模式的区别
2019-04-28
使用Java 8 Stream像操作SQL一样处理数据(上)
2021-07-01
使用Java 8 Stream像操作SQL一样处理数据(下)
2021-07-01
Mybatis-plus 思维导图,让 Mybatis-plus 不再难懂
2021-07-01
MyBatis 思维导图,让 MyBatis 不再难懂(一)
2021-07-01
mybatis思维导图,让mybatis不再难懂(二)
2021-07-01
Spring思维导图,让Spring不再难懂(ioc篇)
2021-07-01
Spring思维导图,让spring不再难懂(一)
2021-07-01
Spring思维导图,让Spring不再难懂(mvc篇)
2021-07-01
小白学数据:教你用Python实现简单监督学习算法
2021-07-01
深度学习工具caffe详细安装指南
2019-04-28
漫画:什么是数据仓库
2019-04-28
漫画:什么是分布式事务
2019-04-28
究竟啥才是互联网架构“高并发”
2019-04-28
TCP接入层的负载均衡、高可用、扩展性架构
2019-04-28
漫画:什么是字典序算法
2019-04-28
MySQL 的索引是什么?怎么优化?
2019-04-28