目录
首先看一个题目,有n个数,取值范围是 0~n,写出一个排序算法,要求时间复杂度和空间复杂度都是O(n)的。
为了达到这种效果,这一篇将会介绍一种不基于比较的排序方法。这种方法被称为计数排序。
计数排序的思路是这样的,对于每一个待排序元素a,如果知道了待排序数组中有多少个比它小的数,那么就可以直接知道在排序后的数组中 a 应该在什么位置上。比如,如果一个数组中有3个数是比a小的,那么,在排序后的数组里,a必然会出现在第4位。
现在问题转化成,对于待排序数组里的一个数,如何能快速知道比它小的数字有多少个。要解决这个问题,我们不能使用比较的办法,那样时间复杂度是无法降下来,只有换一个思路,以空间换时间。因为n个数的取值范围是 0~n,所以,不妨使用一个大小为 n 的数组来统计从0到n,每个数在待排序数组中出现的次数。这个数组类似于直方图数组,因为这种方式也被称做是基于统计的排序。直方图统计的思路简单清晰,在很多题目中都会有出现,一定要熟练掌握这种技巧。
强调:计数排序适合排序一组集中的数据。
- //计数排序
- public static void countSort(int[] array) {
- //1. 找到待排序数组的范围,也就是找到最大值和最小值
- int max = array[0];
- int min = array[0];
- //循环遍历找寻最小值和最大值
- for (int i = 1; i < array.length; i++) {
- if (array[i] > max)
- max = array[i];
- if (array[i] < min)
- min = array[i];
- }
- //计算待排数组的长度
- int len = max - min + 1;
- //2. 定义一个计数数组
- int[] count = new int[len];
- //3. 遍历array数组,把数据计数到计数数组中
- for (int i = 0; i < array.length; i++) {
- count[array[i] - min]++;
- }
- //4. 将array数组还原
- int index = 0;//来控制array数组的下标
- for (int i = 0; i < array.length; i++) {
- //这个循环的作用,是把count里面标记的数据取出来
- while (count[i] > 0) {
- array[index] = i + min;
- index++;
- count[i]--;
- }
- }
- }
-
- public static void main(String[] args) {
- int[] a = {5,4,3,2,1};
- Sort.countSort(a);
- for (int x : a) {
- System.out.print(x + " ");
- }
- }
时间复杂度 | 空间复杂度 |
O(MAN(N,范围)) | O(N) |
对数据的范围敏感 | 对数据的范围敏感 |