什么是计数排序

有一种特殊的排序算法叫计数排序，这种排序算法不是基于元素比较，而是利用数组下标来确定元素的正确位置。

适用场景

它适用于一定范围的整数排序。在取值范围不是很大的情况下，它的性能在某些情况甚至快过那些O(nlogn)的排序，例如快速排序、归并排序。

leetcode习题

点赞最多题解

JAVA代码

import java.util.Arrays;/** * @since 2021-01-04 */public class Code1122 {    public int[] relativeSortArray(int[] arr1, int[] arr2) {        // 由于题目说 arr1 的范围在 0-1000，所以生成一个 1001 大小的数组用来存放每个数出现的次数。        int[] arr = new int[1001];        // 储存答案的数组。        int[] ans = new int[arr1.length];        // 遍历 arr1，把整个arr1的数的出现次数储存在 arr 上，arr 的下标对应 arr1 的值，arr 的值对应 arr1 中值出现的次数。        for (int i = 0; i < arr1.length; i++) {            // 如果遇到了这个数，就把和它值一样的下标位置上 +1，表示这个数在这个下标 i 上出现了 1 次。            arr[arr1[i]] += 1;        }        int size = 0;        // 遍历 arr2，现在开始要输出答案了。        for (int element : arr2) {            // 如果 arr2 的值在 arr 所对应的下标位置出现次数大于 0，那么就说明 arr 中的这个位置存在值。            while (arr[element] > 0) {                // 如果存在值，那就把它加到 ans 中，因为要按 arr2 的顺序排序。                ans[size++] = element;                // 加进去了次数 -1 ，不然就死循环了。                arr[element]--;            }        }        // 如果 arr1 的值不在 arr2 中，那么不能就这么结束了，因为题目说了如果不在，剩下的值按照升序排序。        for (int i = 0; i < arr.length; i++) {            // 同样也是找到大于 0 的下标，然后一直加到 ans 中，直到次数为 0。            while (arr[i] > 0) {                ans[size++] = i;                arr[i]--;            }        }        // 返回最终答案。        return ans;    }    public static void main(String[] args) {        int[] arr1 = {2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19};        int[] arr2 = {2, 1, 4, 3, 9, 6};        Code1122 c = new Code1122();        int[] ans = c.relativeSortArray(arr1, arr2);        for (int a : ans) {            System.out.print(a + " ");        }        System.out.println(" ");        int[] expect = {2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19};        System.out.println(Arrays.equals(ans, expect));    }}