基于比较的排序算法(合并排序、堆排序、快排等)的上限是 O(nLogn),即它们不能比nLogn 做得更好。计数排序是一种线性时间排序算法,当元素在从 1 到 k 的范围内时,它在 O(n+k) 时间内排序。
但如果元素在1 到 n^2的范围内怎么办?
我们不能使用计数排序,因为计数排序需要 O(n^2)的时间,这比基于一些比较排序算法要更差。那么我们怎样才可以在线性时间内对这样的数组进行排序吗?
答案就是基数排序即Radix Sort。基数排序的思想是从数的最低有效位到最高有效位进行逐位排序,注意基数排序内部使用计数排序作为子程序进行排序。
基数排序的例子:
原始未排序列表:170、45、75、90、802、24、2、66
我们先按照每个元素的个位的数字的大小进行排序得到 17 0 , 9 0 , 80 2 , 2 , 2 4 , 4 5 , 7 5 , 6 6
注意我们将802排在2前面是因为在原数组中802在2之前,170和90,45和75也是如此
然后根据每个元素的十位的数字进行排序得到 8 0 2, 2, 2 4, 4 5, 6 6, 1 7 0, 7 5, 9 0
最后按照百位数字排序 2、24、45、66、75、90、1 70、8 02
小于100的数没有百分位所以我们将其看作0
假设输入的元素有d位数。基数排序需要 O(d*(n+b)) 时间,其中 b 是表示数字的基数,例如,对于十进制系统,b 是 10。d 的值是多少?如果 k 是数组中最大的数,则 d 将为 O(log b (k))。所以整体时间复杂度是 O((n+b) * log b (k))。如果k很大的话,基数排序似乎比基于比较的排序的时间复杂度要更高。因此我们需要限制k。让 k <= n^c其中 c 是一个常数。在这种情况下,复杂度变为 O(nLog b (n))。但它仍然无法击败基于比较的排序算法。
如果我们让 b 的值更大呢?使时间复杂度线性化的 b 值应该是多少?如果我们将 b 设置为 n,我们得到的时间复杂度为 O(n)。换句话说,如果数字以 n 为底表示(或者每个数字占用 log 2 (n) 位) ,我们可以对范围从 1 到 n^c的整数数组进行线性时间的排序。
基数排序比快速排序等基于比较的排序算法更可取吗?
假设每个数字有log 2 n 位,则 Radix 的运行时间似乎比快速排序对于大范围的输入数字要好。基数排序中隐藏在渐近符号中的常数因子更高,快速排序更有效地使用硬件缓存。此外,基数排序使用计数排序作为子程序,计数排序需要额外的空间来对数字进行排序。
基数排序的要点:
这里给出了一些关于基数排序的关键点
- 数据必须满足一些假设,例如数据必须在一系列元素之间。
- 输入数组必须具有相同基数和宽度的元素。
- 基数排序基于单个数字或字母位置进行排序。
- 我们必须从最右边的位置开始排序,并在每个位置使用稳定的算法。
- 基数排序不是就地算法,因为它使用临时计数数组。
代码演示:
主程序
计数排序作为子程序
复杂度表:
其他语言实现下载链接:
(包含各种语言:C语言、Python、Java、C++等均有示例)
免费资源下载:Radix Sort