package Sorting.src;

/**
 * @author 梦境迷离
 * @description 计数排序
 *
 *              计数排序 计数排序适用数据范围 计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如
 *              [0~100]，[10000~19999] 这样的数据。
 *              最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
 *
 * @time 2018年4月8日
 */
public class CountSort extends Constant {

    private static long time = 0l;

    public static void main(String[] args) throws Exception {
        Constant.printResult(new CountSort().sort(Constant.array2, Constant.len));
        System.out.println("耗费时间：" + time);//array1：18606,array2：18927 几乎相同

    }

    @Override
    public Object[] sort(Object[] array, int len) {

        return countSort(array);
    }

    /**
     * 计数排序
     * <p>
     * 1.得到最大值与最小值，并计算最大值与最小值之差，制造桶，此时桶的下标i并非真正的元素，而是元素与min之差
     * 2.统计每个元素出现的次数，并记录在桶中
     * 3.对桶中的元素进行取出，注意有重复的元素，而此时元素是i与min之和
     */
    public static Object[] countSort(Object[] arr) {
        long t = System.nanoTime();

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        // 找出数组中的最大最小值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, (int) arr[i]);
            min = Math.min(min, (int) arr[i]);
        }
        // 比max大1
        int help[] = new int[max - min + 1];
        // 找出每个数字出现的次数
        for (int i = 0; i < arr.length; i++) {
            int mapPos = (int) arr[i] - min;
            help[mapPos]++;
        }
        int index = 0;
        for (int i = 0; i < help.length; i++) {
            // 因为可能有重复的数据，所以需要循环
            while (help[i]-- > 0) {
                arr[index++] = i + min;
            }
        }

        time = System.nanoTime() - t;
        return arr;
    }
}