计数排序

学习数据结构与算法
2021-05-17 14:29 · 阅读时长3分钟
小课

计数排序是一种非比较类的排序算法,它有一定的局限性,主要适用于元素的值在一定范围的数据,但是它的效率非常高,时间复杂度是O(N+K),K是数据的范围大小。

算法主要思路是

  1. 首先确定数据的范围,并定义计数数组。
  2. 统计计数数组中的每个元素在原数组中出现次数。
  3. 转换计数数组,将出现次数改为在排序后的数组中的位置。
  4. 根据计数数组,输出排序数组。

下面是数组[1, 4, 1, 5, 3, 3, 1, 2, 7] 的排序过程。

计数排序
计数排序
计数排序
计数排序
计数排序
1/4

计数排序代码实现如下

1import java.util.Arrays;
2
3public class Main {
4
5    public static void main(String[] args) {
6        int[] arr = {1, 4, 1, 5, 3, 3, 1, 2, 7};
7        int[] res = countingSort(arr);
8        System.out.println(Arrays.toString(res));
9    }
10
11    public static int[] countingSort(int[] arr) {
12        /**
13         * 计数数组
14         */
15        int[] count = new int[8];
16        /**
17         * 统计计数数组中元素在原数组中出现次数
18         */
19        for (int item : arr) {
20            count[item]++;
21        }
22        /**
23         * 转换计数数组,将出现次数改为在排序后的数组中的位置
24         */
25        for (int i = 1; i < count.length; i++) {
26            count[i] = count[i] + count[i - 1];
27        }
28        int[] sortedArr = new int[arr.length];
29        /**
30         * 根据位置输出排序数组
31         */
32        for (int item : arr) {
33            sortedArr[count[item] - 1] = item;
34            count[item]--;
35        }
36        return sortedArr;
37    }
38}
注意: 这个Java运行环境不支持自定义包名,并且public class name必须是Main

计数排序比比较类排序最快(O(NlogN))的算法(快速排序、归并排序和堆排序)的效率还有高很多,但是前提是数组元素值在一定范围内,并且这个范围要比数组本身的元素的数量N要小,一旦K大于NlogN,这个优势就不存在了。

计数排序排序算法