计数排序 CountingSort

发布时间:2023年12月31日

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

动画演示 :

案例代码 : (此代码有些瑕疵 , 不能处理负数)

    public static void main(String[] args) {
        //int[] arr = {10, 78, 65, 32, 21, 89, 13, 54, 7, 3};
        //sort(arr);
        int[] brr = {0, 1,1, 7, 8, 9, 10};
        //Tsort(brr, 3);
        CountingSort(brr);
    }

    public static void CountingSort(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        int[] count = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }

        //合并
        int n = 0;
        for (int i = 0; i < max; i++) {
            while (count[i] != 0) {
                arr[n++] = i;
                count[i]--;
            }
        }
        
        //打印
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

?代码 :

    public static void CountingSorts(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
            else if (arr[i] < min)
                min = arr[i];
        }
        int[] count = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;
        }

        //合并
        int n = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0) {
                arr[n++] = min + i;
                count[i]--;
            }
        }

        //打印
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

这期就到这 .

文章来源:https://blog.csdn.net/sytdsqzr/article/details/135317829
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。