计数排序(Counting Sort)详解

2023年 10月 4日 65.3k 0

计数排序(Counting Sort)是一种非比较排序算法,其核心思想是通过计数每个元素的出现次数来进行排序,适用于整数或有限范围内的非负整数排序。这个算法的特点是速度快且稳定,适用于某些特定场景。在本文中,我们将深入探讨计数排序的原理、步骤以及性能分析。

countingSort.jpg

算法原理

计数排序的基本思想是:

  • 计数: 遍历待排序的数组,统计每个元素出现的次数,并将统计结果存储在一个计数数组中。计数数组的索引对应着元素的值,而计数数组中的值表示该元素出现的次数。

  • 累积计数: 对计数数组进行累积计数,即将每个元素的计数值加上前一个元素的计数值,得到每个元素在排序后数组中的位置。这一步确保相同元素的相对顺序不变。

  • 排序: 创建一个与待排序数组大小相同的结果数组,然后遍历待排序数组,根据元素的值在累积计数数组中找到其在结果数组中的位置,将元素放置在结果数组中的正确位置。

  • 算法步骤

    计数排序的具体步骤如下:

  • 扫描待排序数组,确定数组的最大值(max)和最小值(min)。

  • 创建一个计数数组(count),长度为max - min + 1。

  • 第一次遍历待排序数组,统计每个元素出现的次数,将结果存储在计数数组中。

  • 对计数数组进行累积计数,确保计数数组中的每个元素表示小于等于该元素值的元素个数。

  • 创建一个与待排序数组大小相同的结果数组(result)。

  • 第二次遍历待排序数组,根据元素的值在累积计数数组中找到其在结果数组中的位置,将元素放置在结果数组中的正确位置。

  • 将结果数组复制回原始数组,完成排序。

  • Java 实现

    以下是使用Java语言实现计数排序算法的示例代码:

    public class Test {
    
        public static void main(String[] args) {
            int[] arr = new int[]{5,2,3,1,6,7,1,3};
            countingSort(arr);
        }
    
        public static void countingSort(int[] arr){
            System.out.println("原始数组:"+ Arrays.toString(arr));
            //获取排序数组的长度
            int len=  arr.length;
            //获取数组最大元素
            int max = Arrays.stream(arr).max().getAsInt();
            //获取数组最小元素
            int min = Arrays.stream(arr).min().getAsInt();
            //计算计数数组的长度
            int rang = max-min+1;
            //创建计数数组
            int count[] = new int[rang];
            //创建排序后的目标数组
            int result[] = new int[len];
            //计数:统计每个元素出现的次数
            for(int i = 0; i < len; i++){
                count[arr[i]-min]++;
            }
            System.out.println("计数数组:"+ Arrays.toString(count));
            //累计计数:计算每个元素在排序后数组中的位置
            for(int j = 1 ;j = 0; k--){
                result[count[arr[k] - min] -1] = arr[k];
                count[arr[k] - min]--;
            }
            System.arraycopy(result, 0, arr, 0, len);
            System.out.println("排序完成的数组:"+ Arrays.toString(arr));
        }
    }
    

    运行结果为:

    原始数组:[5, 2, 3, 1, 6, 7, 1, 3]
    计数数组:[2, 1, 2, 0, 1, 1, 1]
    累计计数数组:[2, 3, 5, 5, 6, 7, 8]
    排序完成的数组:[1, 1, 2, 3, 3, 5, 6, 7]
    

    这段代码演示了如何使用计数排序算法对整数数组进行排序。计数排序是一种稳定的排序算法,适用于整数范围不大的情况,它的时间复杂度为O(n + k),其中n是待排序数组的大小,k是整数范围(数组中最大元素与最小元素的差值)。

    性能分析

    计数排序的性能分析如下:

    • 平均时间复杂度:O(n + k),其中n是待排序数组的大小,k是整数范围。

    • 最坏时间复杂度:O(n + k)。

    • 最佳时间复杂度:O(n + k)。

    • 空间复杂度:O(n + k),需要额外的计数数组和结果数组。

    • 稳定性:计数排序是一种稳定的排序算法,不改变相同元素的相对顺序。

    使用场景

    计数排序适用于以下情况:

    • 需要排序的数据是整数或有限范围内的非负整数。

    • 待排序数据中存在大量重复元素。

    • 对稳定性排序有要求,即相同元素的相对顺序不变。

    总结

    计数排序是一种高效的非比较排序算法,适用于整数排序和稳定性排序的场景。尽管它对整数范围有一定要求,但在合适的情况下,计数排序能够提供线性时间复杂度的排序性能,相对于其他复杂排序算法来说,它具有独特的优势。因此,在选择排序算法时,应根据数据特点和性能需求来决定是否使用计数排序。

    相关文章

    JavaScript2024新功能:Object.groupBy、正则表达式v标志
    PHP trim 函数对多字节字符的使用和限制
    新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
    使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
    为React 19做准备:WordPress 6.6用户指南
    如何删除WordPress中的所有评论

    发布评论