• 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

经典算法:计数排序算法

武飞扬头像
正经程序员
帮助30

前言

计数排序是一种基于整数的排序算法,用于对键位于特定范围内的数组进行排序。它计算每个不同键值的元素总数,然后使用这些计数来确定每个键值在输出中的位置。

计数排序算法循环遍历项目,计算输入集合中每个键的次数的直方图。然后,它执行前缀和计算,以确定每个键在输出数组中具有该键的项目的起始位置。最后,再次遍历项目,将每个项目移动到输出数组中的排序位置。

我们可以使用计数排序来查找文件中出现频率最高的字母,或者有效地对有限范围的数组进行排序。它经常被用作基数排序算法中的子程序,正因为这个,计数排序需要是一种稳定的排序。

简单理解,假如有10个年龄不同的人,统计出有8个人的年龄比A小,那A的年龄就排在第9位,用这个方法可以得到其他每个人的位置,也就排好了序。当然,年龄有重复时需要特殊处理(保证稳定性),这就是为什么最后要反向填充目标数组,以及将每个数字的统计减去1。计数算法的步骤如下:

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数,存入数组 C 的第 i
  3. 对所有的计数累加(从C 中的第一个元素开始,每一项和前一项相加)
  4. 反向填充目标数组:将每个元素i放在新数组的第C[i]项,每放一个元素就将C[i]减去1.

示例代码

import java.util.Arrays;
 
class Main
{
    /*
      arr ——> 需要排序的数组
      k ——> 在0…k-1范围内
    */
    public static void countsort(int[] arr, int k)
    {
        // 创建一个大小为'n'的整数数组来存储排序后的数组
        int[] output = new int[arr.length];
 
        // 创建一个大小为“k 1”的整数数组,初始化
        int[] freq = new int[k   1];
        
        // 将每个整数的计数存储在freq[]
        // 使用输入数组中每个项的值作为索引,
        for (int i: arr) {
            freq[i]  ;
        }
 
        // 计算每个整数的起始索引
        int total = 0;
        for (int i = 0; i < k   1; i  )
        {
            int oldCount = freq[i];
            freq[i] = total;
            total  = oldCount;
        }
 
        // 复制到输出数组,用相等的键保留输入顺序
        for (int i: arr)
        {
            output[freq[i]] = i;
            freq[i]  ;
        }
 
        // 将输出数组复制回输入数组
        Arrays.setAll(arr, i -> output[i]);
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 4, 2, 10, 10, 1, 4, 2, 1, 10 };
 
        // 数组元素的范围
        int k = 10;
 
        countsort(arr, k);
        System.out.println(Arrays.toString(arr));
    }
}

输出:[1, 1, 2, 2, 4, 4, 10, 10, 10]

与插入排序、选择排序、合并排序、快速排序等其他排序算法不同,计数排序不是比较排序。从上面的代码可以看出,它使用键值作为数组的索引。

简单版本

以下是计数排序的简单版本,它不会产生稳定的排序,即不再保留具有相同键的项目的相对顺序。

import java.util.Arrays;
 
class Main
{
    /*
      arr ——> 需要排序的数组
      k ——> 在0…k-1范围内
    */
    public static void countsort(int[] arr, int k)
    {
        // 在输入数组中,创建一个大小为'k 1'的整数数组来存储每个整数的计数
        int[] freq = new int[k   1];
 
        // 将每个整数的计数存储在freq[]
        // 使用输入数组中每个项的值作为索引,
        for (int i: arr) {
            freq[i]  ;
        }
 
        // 用排序顺序覆盖输入数组
        int index = 0;
        for (int i = 0; i < k   1; i  )
        {
            while (freq[i]-- > 0) {
                arr[index  ] = i;
            }
        }
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 4, 2, 10, 10, 1, 4, 2, 1, 10 };
 
        // 数组元素的范围
        int k = 10;
 
        countsort(arr, k);
        System.out.println(Arrays.toString(arr));
    }
}

输出:[1, 1, 2, 2, 4, 4, 10, 10, 10]

性能

计数排序的时间复杂度为O(n k),其中n是输入的大小,k是输入的范围。由于它使用长度为k 1和的数组n,算法使用的总空间也是O(n k)

k当键的范围明显小于项目总数时,计数排序可以非常节省空间n,但是当键的变化明显大于项目总数时k >> n,计数排序会消耗大量空间。

这篇好文章是转载于:学新通技术网

  • 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
  • 本站站名: 学新通技术网
  • 本文地址: /boutique/detail/tanfbeai
系列文章
更多 icon
同类精品
更多 icon
继续加载