计数排序

一时失言乱红尘 2024-04-18 08:20 150阅读 0赞

技数排序是非比较排序，桶排序的一种

时间复杂度：O(n),空间复杂度O(n)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4NjU2NzA3_size_16_color_FFFFFF_t_70][]

用一个数组，记录每个值出现的次数。

另一个数字把记录的内容倾倒到此数组（桶）里。

不稳定的计数排序

import java.util.Arrays;
    
    /**
     * @Description 不稳定的计数排序
     * @Author calvin
     * @Date 2019/9/3 21:10
     **/
    public class CountSort {
    
        public static void main(String[] args){
            int[] arr = {2,4,2,3,7,1,1,0,0,5,6,9,8,5,7,4,0,9};
    
            int[] result = sort(arr);
            System.out.println(Arrays.toString(result));
        }
    
        private static int[] sort(int[] arr) {
    
            int [] result = new int[arr.length];
    
            int[] count = new int[10];
            for(int i =0;i<arr.length;i++){
                count[arr[i]]++;
            }
            System.out.println(Arrays.toString(count));
            for(int i =0,j=0; i<count.length;i++){
                while(count[i]-- >0)
                    result [j++] = i;
            }
            return result;
        }
    }

稳定的计数算法（像一个倒的斜坡，先分流，再从后往前补）

import java.util.Arrays;
    
    /**
     * @Description 稳定的计数排序
     * @Author calvin
     * @Date 2019/9/3 21:10
     **/
    public class CountSort {
    
        public static void main(String[] args){
            int[] arr = {2,4,2,3,7,1,1,0,0,5,6,9,8,5,7,4,0,9};
    
            int[] result = sort(arr);
            System.out.println(Arrays.toString(result));
        }
    
        private static int[] sort(int[] arr) {
            int [] result = new int[arr.length];
            int[] count = new int[10];
            for(int i =0;i<arr.length;i++){
                count[arr[i]]++;
            }
            System.out.println(Arrays.toString(count));
    //        for(int i =0,j=0; i<count.length;i++){
    //            while(count[i]-- >0)
    //                result [j++] = i;
    //        }
            for(int i=1;i<count.length;i++){
                count[i]=count[i]+count[i-1];
            }
            System.out.println(Arrays.toString(count));
    
            for(int i =arr.length -1;i>=0;i--){
                result[--count[arr[i]]] =arr[i];
            }
            return result;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4NjU2NzA3_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/62747da778ea44fb9473db82d61cad32.png