计数排序(稳定)

一、计数排序

时间复杂度：O(n+k)

空间复杂度：O(n+k)  n:数组长度  k：桶长度

稳定性：稳定

二、使用场景

        量大范围小，例如：求某公司大量员工年龄、高考分数 等等

三、上代码

package sort;

import java.util.Arrays;

/**计数排序(小-->大)
 * @author codelmh
 * @data 2021/11/21
 */
public class CountSort {
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 3, 6, 5, 7, 8, 6, 4, 3, 2, 7, 0, 9, 0, 7};
        //打印数组
        SortUtils.print(countSort(arr));
    }

    /**
     *
     * @param arr
     * @return
     */
    public static int[] countSort(int[] arr){
        //新数组
        int[] newArr = new int[arr.length];
        //计数
        int[] count = new int[10];
        //将数全部都加入 计数数组中
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        System.out.println("count: " + Arrays.toString(count));
        //使用这种排序是不稳定的
//        for (int i = 0, j = 0; i < count.length; i++) {
//            while (count[i]-- > 0) newArr[j++] = i;
//        }
        //累加计数
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i-1];
        }
        System.out.println("count: " + Arrays.toString(count));
        //使用逆序加入就可以保证稳定性
        for (int i = arr.length - 1; i >= 0; i--){
            newArr[ --count[arr[i]]] = arr[i];
        }
        //将排好序的数组返回
        return newArr;
    }

}