题解 | #图片整理# 【计数排序】

计数排序

比较容易想到的是将所有字符输入进入 char[] arr 数组中，然后使用 Arrays.sort(arr); 进行排序。

但是，使用快排的时间复杂度为 $O(nlogn)O(nlogn)$，本题使用计数排序，可以将时间复杂度降为 $O(n)O(n)$

思路如下

• 使用一个大小为 $10+26+26=6210\; +\; 26\; +\; 26\; =\; 62$ 的“桶” bucket 来记录所有字符出现的次数
  • 下标 $[0,9][0,\; 9]$ --> 数字0~9
  • 下标 $[10,35][10,\; 35]$ --> 大写字母A~Z
  • 下标 $[36,61][36,\; 61]$ --> 小写字母a~z
• 计数阶段：从前向后遍历 s，将所有元素放入桶中，统计每个元素的出现次数
• 排序阶段：由于已经定义了 bucket 3 个类型（数字、大写字符、小写字母）的顺序，所以从桶中取出所有元素，即为已排序的顺序

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        /**
         * [0, 9] --> 数字0~9
         * [10, 35] --> 大写字母A~Z
         * [36, 61] --> 小写字母a~z
         */
        int[] bucket = new int[10 + 26 + 26];
        // 计数阶段 --> 元素放入桶中
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                index = c - '0';
            } else if (c >= 'A'&& c <= 'Z') {
                index = c - 'A' + 10;
            } else {
                index = c - 'a' + 36;
            }
            bucket[index]++;
        }
        // 从桶中取出元素 --> 排序
        char c = ' ';
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i]-- > 0) {
                if (i >= 0 && i <= 9) {
                    c = (char) (i + '0');
                } else if (i >= 10 && i <= 35) {
                    c = (char) (i - 10 + 'A');
                } else {
                    c = (char) (i - 36 + 'a');
                }
                System.out.print(c);
            }
        }
        System.out.println();
        in.close();
    }
}

• 时间复杂度为 $O(n)O(n)$
• 空间复杂度为 $O(1)O(1)$