计数排序

计数排序

package org.coral.algorithm.sort;

/**
 *
 1.找出待排序的数组中最大和最小的元素；
 2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项；
 3.对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加）；
 4.反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1.

 */
public class CountSort implements Sort {
    public static void main(String[] args) {
        int[] numbers = {34, 12, 23, 56, 56, 56, 78};
        CountSort countSort = new CountSort();
        countSort.print(numbers);
        countSort.sort(numbers);

    }
    @Override
    public void sort(int[] numbers) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        //找出数组中的最大最小值
        for(int i = 0; i < numbers.length; i++){
            max = Math.max(max, numbers[i]);
            min = Math.min(min, numbers[i]);
        }

        int[] help = new int[max - min + 1];

        //找出每个数字出现的次数
        for(int i = 0; i < numbers.length; i++){
            int mapPos = numbers[i] - min;
            help[mapPos]++;
        }

        //计算每个数字应该在排序后数组中应该处于的位置
        for(int i = 1; i < help.length; i++){
            help[i] = help[i-1] + help[i];
        }

        //根据help数组进行排序
        int res[] = new int[numbers.length];
        for(int i = 0; i < numbers.length; i++){
            int post = --help[numbers[i] - min];
            res[post] = numbers[i];
        }

        print(res);
    }
}