前缀树与非比较排序

import java.util.HashMap;

/**
 * 前缀树的实现：
 * 1. 基本结构
 * 2. 操作集合：插入、删除、查找字符串、计数以xx为前缀的字符串的个数
 *
 */
public class Trie {

    // 节点类
    private static class Node {
        public HashMap<Character, Node> nexts;
        public int pass;
        public int end;

        public Node() {
            pass = 0;
            end = 0;
            nexts = new HashMap<>();
        }
    }

    private Node root;

    public Trie() {
        root = new Node();
    }

    /**
     * 插入元素
     */
    public void insert(String str) {
        if (str == null) {
            return;
        }

        Node curNode = root;
        curNode.pass++;

        for (int i = 0; i < str.length(); i++) {
            char curChar = str.charAt(i);

            if (!curNode.nexts.containsKey(curChar)) {
                curNode.nexts.put(curChar, new Node());
                curNode = curNode.nexts.get(curChar);
            } else {
                curNode = curNode.nexts.get(curChar);
            }
            curNode.pass++;
        }
        curNode.end++;
    }

    /**
     * 删除指定字符串
     */
    public void remove(String str) {
        if (str == null || root == null) {
            return;
        }
        if (countStrNum(str) == 0) {
            return;
        }

        Node curNode = root;
        curNode.pass--;
        for (int i = 0; i < str.length(); i++) {
            char curChar = str.charAt(i);

            if (curNode.nexts.get(curChar).pass - 1 == 0) {
                curNode.nexts.remove(curChar);
                return;
            }

            curNode = curNode.nexts.get(curChar);
            curNode.pass--;
        }
        curNode.end--;
    }

    /**
     * 查找前缀树中存储了字符串str的个数
     */
    public int countStrNum(String str) {
        if (str == null) {
            return 0;
        }

        Node curNode = root;

        for (int i = 0; i < str.length(); i++) {
            char curChar = str.charAt(i);
            if (!curNode.nexts.containsKey(curChar)) {
                return 0;
            }
            curNode = curNode.nexts.get(curChar);
        }
        return curNode.end;
    }

    /**
     * 查找前缀树中以pref为前缀的字符串有多少个
     */
    public int countPrefixNum(String pref) {
        if (pref == null) {
            return 0;
        }

        Node curNode = root;
        for (int i = 0; i < pref.length(); i++) {
            char curChar = pref.charAt(i);
            if (!curNode.nexts.containsKey(curChar)) {
                return 0;
            }
            curNode = curNode.nexts.get(curChar);
        }

        return curNode.pass;
    }

}

import java.util.Arrays;

public class CountSort {

    public void countSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
        }

        int[] count = new int[max + 1];

        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }

        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0) {
                arr[k++] = i;
                count[i]--;
            }
        }
    }

import java.util.Arrays;

public class RadixSort {

    public void radixSort(int[] arr) {

        // 1
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int maxPlace = 0;
        while (max > 0) {
            maxPlace++;
            max /= 10;
        }

        // 2
        for (int curPlace = 0; curPlace < maxPlace; curPlace++) {

            // 2.1
            int[] count = new int[10];
            for (int j = 0; j < arr.length; j++) {
                int curNum = getPlace(arr[j], curPlace);
                count[curNum]++;
            }

            // 2.2
            int[] preSum = new int[10];
            preSum[0] = count[0];
            for (int i = 1; i < preSum.length; i++) {
                preSum[i] = preSum[i - 1] + count[i];
            }

            // 2.3
            int[] help = new int[arr.length];

            // 2.4
            for(int i = arr.length - 1; i >= 0; i--) {
                int curNum = getPlace(arr[i], curPlace);
                help[--preSum[curNum]] = arr[i];
            }

            // 3
            for (int i = 0; i < arr.length; i++) {
                arr[i] = help[i];
            }
        }
    }

    public int getPlace(int num, int place) {
        num /= (int) Math.pow(10, place);
        return num % 10;
    }