189 8069 5689

计数排序（CountingSort）详解

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

十载的平桥网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。成都全网营销的优势是能够根据用户设备显示端的尺寸不同，自动调整平桥建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。创新互联公司从事“平桥网站设计”,“平桥网站推广”以来，每个客户项目都认真落实执行。

算法原理

计数排序的基本思想是：

  1. 计数：遍历待排序的数组，统计每个元素出现的次数，并将统计结果存储在一个计数数组中。计数数组的索引对应着元素的值，而计数数组中的值表示该元素出现的次数。
  2. 累积计数：对计数数组进行累积计数，即将每个元素的计数值加上前一个元素的计数值，得到每个元素在排序后数组中的位置。这一步确保相同元素的相对顺序不变。
  3. 排序：创建一个与待排序数组大小相同的结果数组，然后遍历待排序数组，根据元素的值在累积计数数组中找到其在结果数组中的位置，将元素放置在结果数组中的正确位置。

算法步骤

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

  1. 扫描待排序数组，确定数组的最大值（max）和最小值（min）。
  2. 创建一个计数数组（count），长度为max - min + 1。
  3. 第一次遍历待排序数组，统计每个元素出现的次数，将结果存储在计数数组中。
  4. 对计数数组进行累积计数，确保计数数组中的每个元素表示小于等于该元素值的元素个数。
  5. 创建一个与待排序数组大小相同的结果数组（result）。
  6. 第二次遍历待排序数组，根据元素的值在累积计数数组中找到其在结果数组中的位置，将元素放置在结果数组中的正确位置。
  7. 将结果数组复制回原始数组，完成排序。

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 < rang; j++){
            count[j]+=count[j-1];
        }
        System.out.println("累计计数数组："+ Arrays.toString(count));
        //排序：根据累计计数数组将元素放置到正确的位置
        for(int k = len -1 ; k >= 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)，需要额外的计数数组和结果数组。
  • 稳定性：计数排序是一种稳定的排序算法，不改变相同元素的相对顺序。

使用场景

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

  • 需要排序的数据是整数或有限范围内的非负整数。
  • 待排序数据中存在大量重复元素。
  • 对稳定性排序有要求，即相同元素的相对顺序不变。

总结

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


新闻名称：计数排序（CountingSort）详解
转载源于：http://cdxtjz.cn/article/cojdoio.html

其他资讯