计数排序
收录于
学习数据结构与算法
2021-05-17 14:29 · 阅读时长3分钟
计数排序是一种非比较类的排序算法，它有一定的局限性，主要适用于元素的值在一定范围的数据，但是它的效率非常高，时间复杂度是O(N+K)，K是数据的范围大小。
算法主要思路是
- 首先确定数据的范围，并定义计数数组。
- 统计计数数组中的每个元素在原数组中出现次数。
- 转换计数数组，将出现次数改为在排序后的数组中的位置。
- 根据计数数组，输出排序数组。
下面是数组[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，这个优势就不存在了。
计数排序排序算法
1