排序算法之基数排序

1. 基数排序

  1. 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。
  2. 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法。
  3. 基数排序(Radix Sort)是桶排序的扩展。
  4. 基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个
    位数分别比较。

1.1基数排序基本思想

​ 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

1.1.1 基数排序图文说明

将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序

1.2 代码实现

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * 基数排序的方法
 */
public static void radixSort(int[] arr) {
	/*
	 * 第一步，找到该数组中最大数的位数maxLength
	 * */
	int max = arr[0];
	for (int i = 0; i < arr.length; i++) {
		if(arr[i]>max) {
			max = arr[i];
		}
	}
	int maxLength = (max + "").length();
	
	/*
	 * 第二步，进行排序前准备工作
	 * */
	//排序需要的--桶
	int[][] bucket = new int[10][arr.length];
	
	//记录每个桶中的数的个数
	int[] bucketCounts = new int[10];
	
	
	/*
	 * 第三步，开始排序
	 * */
	for (int i = 0,n =1 ; i < maxLength; i++,n*=10) {//该循环是对 -- 个位--十位--百位的操作
		
		//把数据放入到桶中
		for (int j = 0; j < arr.length; j++) {//按个位对每个元素的操作，按十位...
			
			int digit = arr[j]/ n %10;//n=1得到的是个位  n=10的得到的是十位 n=100
			//bucketCounts[digit]默认为0
			bucket[digit][bucketCounts[digit]] = arr[j];
			
			bucketCounts[digit]++;
			
		}
		
		int index = 0;
		//遍历每一个桶，并把桶中的数据放入到原数组中
		for (int k = 0; k < bucketCounts.length; k++) {
			
			if(bucketCounts[k]!=0) {//如果桶中有数据，就放入到原数组
				for (int j = 0; j < bucketCounts[k]; j++) {
					arr[index++] = bucket[k][j];
				}
			}
			bucketCounts[k] = 0;
		}
		
		//System.out.println("第"+(i+1)+"轮："+Arrays.toString(arr));
	}	
	
}

1.3 测试结果及速度

  • 8w--> 1s不到
  • 80w--> 1s不到
  • 800w-->1s不到
  • 8000w-->java.lang.OutOfMemoryError
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
public class RadixSort {

	/**
	 * 8w--> 1s不到
	 * 80w--> 1s不到
	 * 800w-->1s不到
	 * 8000w-->java.lang.OutOfMemoryError
	 * @param args
	 */
	public static void main(String[] args) {
		//int[] arr = {53,3,542,748,14,214};
		
		
		 int[] arr = new int[80000000]; 
		 for (int i = 0; i < 80000000; i++) { 
			 arr[i] =(int)(Math.random()*800000); 
		 } 
		 
		 Date date1 = new Date(); SimpleDateFormat
		 simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		 
		 String format1 = simpleDateFormat.format(date1);
		 System.out.println("排序前的时间："+format1);
		 
		 int[] temp = new int[arr.length];
		 radixSort(arr);
		
		 Date date2 = new Date();
		 String format2 = simpleDateFormat.format(date2);
		 System.out.println("排序后的时间："+format2);
	}
}

1.3 基数排序注意点

  • 基数排序是对传统桶排序的扩展，速度很快.
  • 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
  • 基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的
  • 有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9