当前位置 : 主页 > 编程语言 > 其它开发 >

计数排序的简单理解

来源:互联网 收集:自由互联 发布时间:2022-06-29
学习计数排序可以了解到空间换时间的思想,其是一种牺牲空间换时间的排序算法,在其特定的场景上,甚至将时间复杂度降到了线性级别。 详细描述 计数排序作为一种线性时间复杂
学习计数排序可以了解到空间换时间的思想,其是一种牺牲空间换时间的排序算法,在其特定的场景上,甚至将时间复杂度降到了线性级别。 详细描述

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

计数排序详细的执行步骤如下:

  1. 找出原数组中元素值最大的,记为 max
  2. 创建一个新数组 count,其长度是 max+1,其元素默认值都为 0
  3. 遍历原数组中的元素,以原数组中的元素作为 count 数组的索引,以原数组中的元素出现次数作为 count 数组的元素值;
  4. 创建结果数组 result,起始索引 index
  5. 遍历 count 数组,找出其中元素值大于 0 的元素,将其对应的索引作为元素值填充到 result 数组中去,每处理一次,count 中的该元素值减 1,直到该元素值不大于 0,依次处理 count 中剩下的元素;
  6. 返回结果数组 result
算法图解

计数排序

问题解疑 计数排序的时间复杂度是多少?

计数排序的时间复杂度可以达到 \(O(n+k)\),其中 k 是 count 数组的长度。

从这里可以知道,count 数组元素的取值越集中,算法耗费的时间越短。

计数排序有什么限制吗?

计数排序有两个前提需要满足:

  • 排序的元素必须是整数,否则无法对应数组的索引下标
  • 排序元素的取值要在一定范围内,并且比较集中,否则 count 数组将会非常大

只有这两个条件都满足,才能最大程度发挥计数排序的优势。

代码实现
package cn.fatedeity.algorithm.sort;

/**
 * 计数排序算法
 */
public class CountSort {
    public static int[] sort(int[] numbers) {
        if (numbers.length == 0) {
            return numbers;
        }

        int min = numbers[0], max = numbers[0];
        for (int number : numbers) {
            if (number < min) {
                min = number;
            } else if (number > max) {
                max = number;
            }
        }

        int[] count = new int[max - min + 1];
        for (int number : numbers) {
            int index = number - min;
            count[index]++;
        }

        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                numbers[index++] = i + min;
                count[i]--;
            }
        }

        return numbers;
    }
}

首发于翔仔的个人博客,点击查看更多。

上一篇:题解 洛谷P1762 偶数/6.21校内考试T2
下一篇:没有了
网友评论