与基于比较的排序算法(归并排序、堆排序、快速排序、冒泡排序、插入排序等等)相比,基于比较的排序算法的时间复杂度最好也就是
,而且不能比
更小了。
计数排序(Counting Sort)的时间复杂度为
量级,更准确的说,计数排序的时间复杂度为
,其中
表示待排序元素的取值范围(最大与最小元素之差加 1 )。
那么问题来了,当这个元素的的范围在 1 到
怎么办呢?
此时就不能用计数排序了奥,因为这种情况下,计数排序的时间复杂度达到了
量级。
比如对数组 [170, 45, 75, 90, 802, 24, 2, 66]
这个而言,数组总共包含 8 个元素,而数组中的最大值和最小值之差为 802 - 2 = 800
,这种情况下,计数排序就 ”失灵了“ 。
那么有没有那种排序算法可以在线性时间对这个数组进行排序呢?
答案就是今天要讲的 基数排序(Radix Sorting) 。基数排序的总体思想就是从待排序数组当中,元素的最低有效位到最高有效位 逐位 进行比较排序;此外,基数排序使用计数排序作为一个排序的子过程。
下面我们就以数组 [170, 45, 75, 90, 802, 24, 2, 66]
,快乐学习基数排序!
数组当中的最大值 802 为三位数,所以我们在不足三位的数字前面补 0 ,即[170, 045, 075, 090, 802, 024, 002, 066]
方便后续说明基数排序。
第一步:按数组当中元素的最低有效位,个位 [170 ,045 ,075 , 090 ,802 , 024 , 002 , 066 ],进行计数排序:
第二步:按数组当中元素的次最低有效位,十位数 [170, 090, 802, 002, 024, 045, 075, 066] ,进行计数排序:
第三步:按数组当中元素的最高有效位,百位 [802, 002, 024, 045, 066, 170, 075, 090] ,进行计数排序:
这样我们就完成了基数排序,得到了一个有序数组 [2, 24, 45, 66, 75, 90, 170, 802] .
import java.io.*;
import java.util.*;
class Radix {
// 获取数组中的最大值
static int getMax(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
max = arr[i];
return max;
}
// 计数排序
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; //输出数组
int i;
int count[] = new int[10];
Arrays.fill(count,0);
// 统计数组中元素第 exp 位的数目
for (i = 0; i < n; i++){
count[(arr[i]/exp)%10]++;
}
// 对 count[] 数组进行转
for (i = 1; i < 10; i++){
count[i] += count[i - 1];
}
// 进行计数排序
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// 输出到数组arr[]中
for (i = 0; i < n; i++){
arr[i] = output[i];
}
}
// 基数排序
static void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// 对数组当中的数字按照每一个有效位进行一趟计数排序。
for (int exp = 1; m/exp > 0; exp *= 10){
countSort(arr, n, exp);
}
}
// 进行输出
static void print(int arr[], int n)
{
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}
/*Driver function to check for above function*/
public static void main (String[] args)
{
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = arr.length;
radixsort(arr, n);
print(arr, n);
}
}
实现当中有一个细节需要解释一下,那就是如何从最低位到最高位取每一个数字的该位的值。答案很简单了,就是除 10 取余。
比如 802 ,要取最低位,802 % 10 = 2
,就取到了个位;紧接着除 10 取商数 802 / 10 = 80 ,然后对商数 80 进行除 10 取余数,就可以得到十位了,80 % 10 = 0 ;最后再对 80 除 10 取商数 80 / 10 = 8 , 然后对商数 8 进行除 10 取余数,8 % 10 = 8 就可以得到百位数。
代码中的 (arr[i] / exp) % 10
就可以轻松理解啦, exp
就相当于控制位数,而取余操作就相当于取出第 exp
位的值。
当然彻底搞懂基数排序,前提是你要清楚计数排序(Counting Sort),又到打广告的时间了,推荐看一下 漫画:什么是计数排序?。
设
表示输入的数组当中最大值的位数(比如 802,3位,
),那么基数排序的时间复杂度就是
,其中
表示数组的长度,而
则是表示一个数的基础,对十进制而言,
;
设
是一个计算机可表示的最大整数,那么
;
则基数排序整个时间复杂度为
。
对于一个较大的数
,计数排序的这个时间复杂度似乎比基于比较的排序算法都慢,但是事实未必,接着看。
假设
取一个最大整数,其中
是一个常量;
那么基数排序的时间复杂度就为
,其中
和
都是常数,我们可以忽略不计,那么基数排序的时间复杂度就变成了
,但是这依旧不比基于排序算法的最好时间复杂度
好呀?
可是当我们将这个
取足够大呢?
取多少的时候基数排序的时间复杂度才能变成线性呢?
当
的时候,
,基数排序的时间复杂度就变成了
,线性时间复杂度。
也就说,当数字用
进制表示的时候,我们就可以对 1 到
范围之内的数组进行线性排序。
对于元素的跨度(范围)比较大的数组而言,基数排序的运行时间可能比快速排序要好。但是对于基数排序而言,其渐近时间复杂度中隐含了更高的常量因子,并非完全的线性;而快速排序更有效地利用硬件缓存,提高其效率。此外,基数排序使用计数排序作为子过程,计数排序占用额外的空间来对数组进行排序。
但是基数排序解决我们最开始所提出的问题,当数据范围在 1 到
时,计数排序的复杂度将变为
量级,而基数排序依旧可以在线性时间进行排序!
计数排序使用了额外的空间进行排序,空间复杂度为
。
---