新闻动态
NEWS

一.算法简介

       经由过程统计元素呈现的次数进而排序，须要一个帮助数组，大小是最大元素值（想想计数的过程），为了更好的懂得计数排序，我们先来想象一下若是一个数组里所有元素都长短负整数（数组下标是整数），并且都在0-max（因为内存的原因，这个值要小一些）以内，那对于数组里每个元素来说，若是我能知道数组里有几许项小于或便是该元素，就能正确地给出该元素在排序后的数组的地位。

        局限性：经由过程上方的描述可以看出须要非负整数，并且最大值要在能开数组局限内。

        算法是稳定的，算法第五步从后往前包管了稳定性，读者细细领会……

二.算法描述

1. 求得元素最大值max（看算法实现过程，领会这个办法须要自力，就是说max须要事先断定）


2. 开帮助数组c[max]和res[原数组大小]并全部初始化为0


3. 计数：统计元素呈现次数并把次数放在c数组的以该元素为下标的地位


4. 针对c数组从下标1开端，前一项加上后一项并存入后一项获得数组里有几许项小于或便是该元素


5. 对原数组中的每一个元素temp存入res[c[temp]-1]（减一是因为下标从0开端）并更新c[temp]--（不必愁闷小于0，因为一旦便是0就不会再减小了，因为原数组没该元素了）

三.算法的Java实现

public class CountSort {

    public static void main（String[] args） {

        int[] a = { 3， 1， 6， 0， 3， 0， 1， 5， 3， 6 };

        int max = getMax（a）;

        arrDisplay（a， Before mySort:）;

        a = mySort（a， max）;

        arrDisplay（a， After  mySort:）;

    }



    public static int[] mySort（int[] a， int max） {

        int[] res = new int[a.length];

        int[] c = new int[max + 1];

        for （int i = 0; i < res.length; i++） {

            res[i] = 0;

        }

        for （int i = 0; i < c.length; i++） {

            c[i] = 0;

        }

        int temp = 0;

        /统计元素呈现次数并把次数放在c数组的以该元素为下标的地位

        不成以在这个遍历过程中取最大值，就是说getMax不成归并，因为须要事先c的大小；

        可否直接开为整形最大值，如许不成能，超内存/

        for （int i = 0; i < a.length; i++） {

            temp = a[i];

            c[temp] = c[temp] + 1;

        }

        for （int i = 1; i < c.length; i++） {

            c[i] = c[i] + c[i - 1];

        }

        

        //必须从后往前，如许包管了稳定性

        for （int i = a.length - 1; i >= 0; i--） {

            temp = a[i];

            res[c[temp] - 1] = temp;

            //不必愁闷小于0，因为一旦便是0就不会再减小了，因为原数组没该元素了

            c[temp] = c[temp] - 1;

        }

        return res;

    }



    public static int getMax（int[] a） {

        int max = a[0];

        for （int i = 1; i < a.length; i++） {

            if （a[i] > max）

                max = a[i];

        }

        return max;

    }



    public static void arrDisplay（int[] a， String str） {    

        System.out.println（str）;

        for （int i = 0; i < a.length; i++）

            System.out.print（a[i] +  ）;

        System.out.println（）;

    }

}