什么是计数排序
计数排序是一种利用数组下标来确定元素的正确位置的排序算法。
算法实现
1、根据数组中最大的元素的值 length，创建一个额外的长度为 length + 1 的数组，该数组的初始值均为 0。
2、遍历原数组，通过原数组的值，找到新开辟的数组的位置，将该位置的元素值进行 +1 操作。
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
27
| public static void main(String[] args) {
SortRunner.run(SortUtils.generateRandomArray(10000, 100, 1000),
(arr) -> {
countSort(arr);
});
}
private static void countSort(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int[] countArray = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
countArray[arr[i]]++;
}
int index = 0;
for (int i = 0; i < countArray.length; i++) {
for (int j = 0; j < countArray[i]; j++) {
arr[index++] = i;
}
}
}
|
计数排序优化
在上述的计数排序中，有一个问题，就是原数组的最小值是 100，最大值是 1000，而用于计数的数组长度开辟为 length + 1，这样一来，计数数组 0-99 的索引空间就被浪费了。
所以可以对计数排序进行一些优化，获取数组的最小值，作为计数数组的偏移量，用于计算整数在计数数组中的下标。
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
| public static void main(String[] args) {
SortRunner.run(SortUtils.generateRandomArray(10000, 100, 1000),
(arr) -> {
countSort(arr);
});
}
private static void countSort(int[] arr) {
int max = arr[0];
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
int[] countArray = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
countArray[arr[i] - min]++;
}
int index = 0;
for (int i = 0; i < countArray.length; i++) {
for (int j = 0; j < countArray[i]; j++) {
arr[index++] = i + min;
}
}
}
|
稳定排序
什么是稳定排序？
稳定排序是指，在需要排序的元素之中，值相同的元素可以保持原本的相对位置，这种排序就被称作稳定排序。
上述的计数排序并不是稳定排序，可以通过再次进行优化，而使计数排序变成一种稳定排序。
为了使计数排序变成稳定排序，需要对计数数组进行变形，从计数数组的第二个元素开始，每一个元素都加上前面所有元素之和。
这样做的目的是使得计数数组的元素值，由原本对应的整数的个数，变成对应整数的最终排序的序号。
计数数组变形之和，从后往前遍历原数组，将原数组找到计数数组的值，从而将元素放入一个新的数组中，并将计数数组对应的值 -1。
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
| public static void main(String[] args) {
SortRunner.run(SortUtils.generateRandomArray(10000, 100, 1000),
(arr) -> {
countSort(arr);
});
}
private static void countSort(int[] arr) {
int max = arr[0];
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
int[] countArray = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
countArray[arr[i] - min]++;
}
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
int[] sortArray = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
int sort = countArray[arr[i] - min];
sortArray[sort - 1] = arr[i];
countArray[arr[i] - min]--;
}
System.arraycopy(sortArray, 0, arr, 0, arr.length);
}
|
计数排序的复杂度
元素数组的规模为 n，最大和最小整数的差值是 m，则计数排序的时间复杂度和空间复杂度为：
时间复杂度为：O(n+m)
空间复杂度为：O(m)
计数排序的局限性
计数排序的速度非常快，但是有一定的局限性。
1、当原始数组的规模最大值和最小值差距过大时，计数排序并不适用，因为差值过大的时候，会严重浪费空间，而且计数数组过大，也会增加时间复杂度。
2、当原始数组的值不是整数的时候，也不适用计数排序，因为计数排序需要通过值来找到对应的索引，而小数找不到对应的索引。
最后
本文Github https://github.com/herenpeng/code-learn 已收录，欢迎Star。
