码农戏码

新生代农民工的自我修养

0%

算法渣-排序-基数排序

Posted on Edited on

没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

线性排序

常见的三种以线性时间运行的算法：计数排序、基数排序和桶排序；

需要注意的是线性排序算法是非基于比较的排序算法，都有使用限制才能达到线性排序的效果

定义

基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机（Tabulation Machine）, 排序器每次只能看到一个列。它是基于元素值的每个位上的字符来排序的。 对于数字而言就是分别基于个位，十位， 百位或千位等等数字来排序。

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数

算法

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较

基数排序可以采用两种方式：

LSD（Least Significant Digital）：从待排序元素的最右边开始计算（如果是数字类型，即从最低位个位开始）

MSD（Most Significant Digital）：从待排序元素的最左边开始计算（如果是数字类型，即从最高位开始）

基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。

等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成

演示

通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}，它的示意图如下：

在上图中，从最低位开始，依次进行排序。

  1. 按照个位数进行排序。
  2. 按照十位数进行排序。
  3. 按照百位数进行排序。
    排序后，数列就变成了一个有序序列

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Radix-Sort(A, d)
// 每个在数组A[1...n] 中的元素都是d-位数的正整数
// 位数是从右到左标记上1到d 的
//A[]-- 初始的待排序的数组

   // 创建一个for 循环，从1 到d
   for j = 1 to d do
       int count[10] = {0};
       // 将键的计数放在数组count[] 中
       // 键key - 是在位数j 上的数字
       for i = 0 to n do
          count[key of(A[i]) in pass j]++
       for k = 1 to 10 do
          count[k] = count[k] + count[k-1]
 
      // 创建一个结果数组，通过从count[k] 中检查A[i] 中的新位置
      for i = n-1 downto 0 do
          result[ count[key of(A[i])] ] = A[j]
          count[key of(A[i])]--
 
     //现在主数组A[] 包含了根据现在位数位置排好序的数字
     for i=0 to n do
         A[i] = result[i]
 
   end for(j)
end func

实现

使用桶排序，把各位上的数分别桶排序，再依次输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private static void radixSort(int []array){
	//取最大值，好计算位数
	int max = Integer.MIN_VALUE;
	for (int a:array) {
		if(a> max) {
			max = a;
		}
	}
	//(0~9)10个桶
	int [][]buckets = new int[10][];

	//初始化桶
	for(int b=0;b<10;b++) {
		buckets[b] = new int[array.length];
	}

	//每个桶的元素数量
	int [] index = new int[10];
	//按每一位数排序
	for (int radix = 1;max/radix>0;radix*=10){
		//把元素放到各自的桶内
		for (int a:array) {
			//得到每位数
			int per = a/radix%10;
			buckets[per][index[per]] = a;
			index[per]++;
		}
		//各个桶的数据依次放回数组
		int j = 0;
		for (int b=0;b<10;b++) {
			//去掉桶中别的元素
			for (int i = 0;i<index[b];i++){
				array[j++] = buckets[b][i];
			}
		}
		System.err.println("按第"+radix+"位,排序：" + Arrays.toString(array));
		//清空计数器
		index = new int[10];
	}
}

对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}进行基数排序

通过程序可以看出每位数排序的结果

1
2
3
按第1位,排序：[542, 53, 3, 63, 14, 214, 154, 616, 748]
按第10位,排序：[3, 14, 214, 616, 542, 748, 53, 154, 63]
按第100位,排序：[3, 14, 53, 63, 154, 214, 542, 616, 748]

百倍排序完，整个数组也就排序好了

复杂度

时间复杂度

假设在基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))。

空间复杂度

在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间