当前位置: 代码迷 >> 综合 >> 线性时间排序——基数排序、桶排序
  详细解决方案

线性时间排序——基数排序、桶排序

热度:40   发布时间:2023-12-12 23:58:47.0

之前一直以为基数排序就是桶排序,但是看了书发现还是有不同的。

基数排序

主要思想是按照位数划分,在每一位中按照计数排序的思想来进行。

主要是应用于卡片排序机上(具体是啥不清楚了,但是貌似也是和计算有关的)

例:321 986 123 432 543 018 765 678 987 789 098 890 109 901 210 012

1.只看个位数,因为只有0-9这几种可能,每一种都给一个数组来存储:
Q[0]:890 210
Q[1]:321 901
Q[2]:432 012
Q[3]:123 543
Q[4]:
Q[5]:765
Q[6]:986
Q[7]:987
Q[8]:018 678 098
Q[9]:789 109
数组内部的顺序可以不考虑,然后将数据按照数组下标0-9的顺序读取放回原数组。
(不考虑顺序是不需要内部排序,但是先来后到的顺序还是要有的,后面会讲)

2.将数据按照十位数来排序:
Q[0]:901 109
Q[1]:210 012 018
Q[2]:321 123
Q[3]:432
Q[4]:543
Q[5]:
Q[6]:765
Q[7]:678
Q[8]:986 987 789
Q[9]:890 098
再放回

3.按照最高位
Q[0]:012 018 098
Q[1]:109 123
Q[2]:210
Q[3]:321
Q[4]:432
Q[5]:543
Q[6]:678
Q[7]:765 789
Q[8]:890
Q[9]: 901 986 987

当我们再次放回的时候,奇迹发生了,数据变得有序了!

实现

数组存储原始数据,因为只有0-9的位数,我们考虑建一个邻接表。
最左边的列为0-9的数组,然后使用链表的形式来尾插(尾插才能保证是有序的,如果第一次排序完整一个头插法,最后的顺序可能会乱掉)
邻接表是最开始在树的存储最早提到的
在这里插入图片描述
这样的方式比较精致,如果空间足够完全可以直接二维数组……
剩下的空间基本上就没什么了。

分析

时间复杂度当然是O(n)了
具体的话,一个是位数d,另一个是每一位的可能种类k(不一定都是十进制的),那么此时的时间复杂度应该为θ(d(n+k))

声明一下,尽管做到了o(n),但是因为余项的问题,所以基数排序和快排相比还是有很多的不足。

空间复杂度为O(n),因为创建了邻接表,所以应该有一部分余项
(不会吧不会吧,不会真的有人有二维数组吧)

稳定,当然稳定了,毕竟相同的数每次都排在同一个数组中(这时应该叫链表),而且是尾插法不改变顺序。

桶排序

之前也有将桶排序和基数排序当成一个,将邻接表里面的链表称为桶,但是细分还是有所不同的。
首先,桶排序的前提限定了数据范围,并希望数据是在每一个范围内是均匀分布的。

先创建桶,然后还是利用邻接表来划分,在每一个划分里面使用任意一种排序,最后合并。

时间复杂度O(n),并且因为相同元素在一个区间,所以稳定不稳定全看内部排序方法。