欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

排序算法之计数排序

程序员文章站 2022-04-16 16:30:47
思想: 计数排序,顾名思义,计算待排序元素中每个元素的数量来排序,用数组的下标作为元素,数组下标对应的值作为该元素出现的次数。实现逻辑:1、获取数组中的最大值来创建一个计数数组用于计数2、遍历待排序数组-----》计算每个元素出现的次数3、建立一个原数组长度的数组作为排序结果4、按计数数组的下标和值将结果放入结果数组import java.util.Arrays;public class CountSort { /** * 1、稳定排序 * 2、时间复杂度O(n...

思想: 计数排序,顾名思义,计算待排序元素中每个元素的数量来排序,用数组的下标作为元素,数组下标对应的值作为该元素出现的次数。

实现逻辑:
1、获取数组中的最大值来创建一个计数数组用于计数
2、遍历待排序数组-----》计算每个元素出现的次数
3、建立一个原数组长度的数组作为排序结果
4、按计数数组的下标和值将结果放入结果数组
5、优化: 假设待排序数组中元素最大100007,最小100000,那么其实我们只需要一个空间为7的数组即可

import java.util.Arrays;

public class CountSort {

    /**
     * 1、稳定排序
     * 2、时间复杂度O(n+K)
     * 3、非原地排序
     * 4、空间复杂度O(K)
     */
    public static void main(String[] args) {
        int[] arr = new int[]{2,3,3,3,3,2,2,2,4,5,6,7,7,8,9,17};
        int[] sortedArr = CountSort.countSort(arr);
        System.out.println(Arrays.toString(sortedArr));
    }

    public static int[] countSort(int[] arr) {
        // 1、获取数组中的最大值
        int maxValue = arr[0];
        int minValue = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxValue) {
                maxValue = arr[i];
            }
            if (arr[i] < minValue) {
                minValue = arr[i];
            }
        }
        //2、创建大小合适的数组作为统计数组
        int[] countdArr = new int[maxValue+1-minValue];
        //3、遍历待排序数组统计
        for (int i = 0; i < arr.length; i++) {
            countdArr[arr[i]-minValue]++;
        }

        //4、遍历统计数组,输出结果
        int index = 0;
        int[] sortedArr = new int[arr.length];
        for (int i= 0; i < countdArr.length; i++) {
            for(int j = 0; j < countdArr[i]; j++) {
                sortedArr[index++] = i + minValue;
            }
        }
        return sortedArr;
    }

}

本文地址:https://blog.csdn.net/H838071332/article/details/107684666

相关标签: 算法