数据结构与算法-排序(九)基数排序(Radix Sort)

摘要

基数排序是进行整数序列的排序,它是将整数从个位开始,直到最大数的最后一位截止,每一个进位(比如个位、十位、百位)的数进行排序比较。

每个进位做的排序比较是用计数排序的方式处理,所以基数排序离不开计数排序。

逻辑

对整数依次从个位数、十位数...进行排序。基数排序非常适合用于整数排序

对每一轮的排序可以使用计数排序的方法处理

基数排序和计数排序来做个简单的比较时,可以看到基数排序每一个进位都要进行一次计数排序,所以比较循环多一些。但是每个进制上的数范围是 0 到 9 这 10 个数,所以需要开辟的空间相对可控和少一些。下面来详细了解一下

流程

  1. 获取序列中的最大值,确定排序的最大位数
  2. 从个位起,使用计数排序的方式处理序列

实现

找出最大值, max 的初始值为序列的 first 元素。循环从 1 开始。

	int max = array[0];
	for (int i = 1; i < array.length; i++) {
		if (array[i] > max) {
			max = array[i];
		}
	}

对序列从个位开始排序(计数排序的方式)。这里要留意,divider 的每一次增加是 divider *= 10,相当于向前进一位。

这里的每一轮比较排序中,交换的是序列中的元素,而不是某个进位上的数字,这个要特别注意。


	for (int divider = 1; divider <= max; divider *= 10) {
		CountingSort(divider);
	}

下面的排序就是用计数排序来处理,对计数排序不太明白的可以看上一期介绍计数排序。

这里有两点需要留意:

  1. 这里直接开辟了 10 个存储空间,是因为,每一个进位上的数只有 0 到 9 这 10 个数
  2. 这里通过 divider % 10 这个方式获取到该进位上的数字。

	private void CountingSort(int divider) {
		
		// 开辟内存空间,存储次数
		int[] counts = new int[10];
		// 统计每个整数出现的次数
		for (int i = 0; i < array.length; i++) {
			counts[array[i] / divider % 10]++;
		}
		// 累加次数
		for (int i = 1; i < counts.length; i++) {
			counts[i] += counts[i-1];
		}
		
		// 从后往前遍历数组,放在有序数组中的位置
		int[] newArray = new int[array.length];
		for (int i = array.length - 1; i >= 0; i--) {
			newArray[--counts[array[i] / divider % 10]] = array[i];
		}
		// 将有序数组覆盖到 array
		for (int i = 0; i < newArray.length; i++) {
			array[i] = newArray[i];
		}
	}

时间和空间复杂度

  • 最好、最坏、平均时间复杂度:O(d*(n+k))
  • 空间复杂度:O(n+k)
  • 属于稳定排序

d 是最大值的位数,k 是进制

数据结构与算法-排序(九)基数排序(Radix Sort)

上一篇:查找算法测试代码


下一篇:【后端】SpringMVC Controller(接口定义 & 注解开发)