java 计数排序

阳光穿透心脏的1/2处 2022-11-21 07:04 152阅读 0赞

--------------------

### java 计数排序 ###

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**计数排序**

![20201031092310798.png][]

**算法描述：找出数组的最大值max、最小值min，创建数组count（长度为max-min+1）**

**遍历原数组元素，数值减去min，**可得count中的索引位index，索引位的数值加1；

**遍历count数组，索引位+min可得原数值，**count数组index为的数值为数据出现个数，将数据还原到原数组中，排序完成

**说明：基数排序适用于整数，且max-min相差不大的场景**

**空间复杂度：**计数排序需要使用**max-min+1的额外空间**

**时间复杂度：o(n)**

**算法稳定性：**计数排序是**稳定的排序算法**

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**示例**

public class MyTest9 {
    
        public static int[] generate(int length){
            int[] a=new int[length];
    
            Random random=new Random();
            for (int i=0;i<length;i++){
                a[i]=random.nextInt(1000);
            }
    
            return a;
        }
    
        public static void countSort(int[] a){
            int min=a[0],max=a[0];
    
            for (int value : a) {
                if (min > value) {
                    min = value;
                }
    
                if (max < value) {
                    max = value;
                }
            }
    
            if (min==max){
                return;
            }
    
            int[] count=new int[max-min+1];
            for (int value : a){
                count[value-min]++;
            }
    
            int index=0;
            for (int i=0;i<count.length;i++){
                if (count[i]!=0){
                    while (count[i]-- > 0){
                        a[index++]=i+min;
                    }
                }
            }
        }
    
        public static void main(String[] args){
            int[] a=generate(10);
            System.out.println("数组排序前为：");
            Arrays.stream(a).forEach(i -> System.out.print(i+" "));
    
            countSort(a);
            System.out.println("\n\n数组排序后为：");
            Arrays.stream(a).forEach(i -> System.out.print(i+" "));
        }
    }

**控制台输出**

数组排序前为：
    607 485 993 643 952 695 851 655 822 195 
    
    数组排序后为：
    195 485 607 643 655 695 822 851 952 993

[20201031092310798.png]: /images/20221120/cbc56ef024934e99a0bbed486b3b56bd.png