十大排序之Counting Sort 计数排序

简介: 十大排序之Counting Sort 计数排序

Counting Sort 计数排序

计数排序(Counting Sort)是一种线性时间复杂度的排序算法,适用于一定范围内的整数排序。其思路如下:

统计数组中每个元素出现的次数,并将统计结果存储在一个辅助计数数组中。

根据辅助计数数组的统计结果,重新构建排序后的数组。

以下是计数排序的具体步骤:

找出待排序数组中的最大值和最小值,确定计数数组的大小。

统计数组中每个元素出现的次数,并将统计结果存储在辅助计数数组中。

对辅助计数数组进行累加操作,以确定每个元素在排序后的数组中的位置。

从待排序数组的末尾开始遍历,根据元素的值和辅助计数数组中的累加值确定元素在排序后数组中的位置,并将元素放置到正确的位置。

以下是计数排序的示例代码:

public class Sort {
    public static void countingSort(int[] arr) {
        int n = arr.length;
        // 找出最大值和最小值
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        // 计算计数数组的大小,并统计每个元素的出现次数
        int range = max - min + 1;
        int[] count = new int[range];
        for (int i = 0; i < n; i++) {
            count[arr[i] - min]++;
        }
        // 对计数数组进行累加操作
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }
        // 构建排序后的数组
        int[] sorted = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            sorted[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }
        // 将排序结果拷贝回原数组
        System.arraycopy(sorted, 0, arr, 0, n);
    }
    public static void main(String[] args) {
        int[] array = {5, 2, 8, 12, 1, 6};
        countingSort(array);
        System.out.println("排序结果:");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

计数排序的时间复杂度为O(n + k),其中n是待排序数组的大小,k是待排序数组中元素的范围。

计数排序的空间复杂度为O(n + k),其中n是待排序数组的大小,k是待排序数组中元素的范围。

计数排序是一种稳定的排序算法,适用于元素范围较小的情况。

相关文章
|
6月前
|
搜索推荐 算法 Java
sort-03-SelectSort 选择排序算法详解
这是一个关于排序算法的系列文章摘要,包括了各种排序算法的介绍和Java实现。文章列举了冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序以及大文件外部排序的链接和简要说明。其中,选择排序算法被详细解释,它是通过找到未排序序列中的最小元素并将其放到正确位置来逐步构建有序序列的。Java实现中,选择排序的`doSort`方法通过两层循环实现,时间复杂度为`O(N^2)`,是稳定的排序算法。整个排序项目已开源在GitHub。
|
6月前
|
人工智能 搜索推荐 算法
sort-04-heap sort 堆排序算法详解
这是一个关于排序算法的系列文章摘要,包括了10篇关于不同排序算法的链接,如冒泡排序、快速排序、选择排序、堆排序等。堆排序是一种基于比较的排序算法,利用了近似完全二叉树的结构并满足最大堆或最小堆的性质。最大堆中,每个节点的值都大于或等于其子节点。文章详细解释了最大堆的概念、节点访问方式以及堆的操作,包括堆调整和堆排序的过程,并通过图解展示了堆排序的具体步骤。此外,还提供了一个Java实现的堆排序代码示例。整个排序系列来源于一个开源项目,读者可以通过链接查看完整内容。
sort-04-heap sort 堆排序算法详解
|
6月前
|
搜索推荐 算法 Java
sort-08-counting sort 计数排序
这是一个关于排序算法的系列文章摘要。文章详细介绍了多种排序算法,包括冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序以及大文件外部排序。计数排序是一种线性时间复杂度的稳定排序算法,由 Harold H. Seward 在1954年提出。基础版计数排序通过创建一个与最大元素等长的新数组来统计每个元素出现的次数,然后填充排序结果。改良版则考虑了空间浪费问题,通过找出最小值来减少数组长度。此外,还提出了使用 TreeMap 来扩展排序算法以适应非数字元素的情况。
|
6月前
|
搜索推荐 算法
Sort-00-十大排序算法汇总
这是一个关于排序算法的系列文章总结,包括冒泡、选择、插入、归并、快速、堆、希尔、计数、桶和基数排序的详细讲解。十大排序算法各有特点,如冒泡排序适合小规模或基本有序的数据,快速排序在大规模随机数据中表现优秀。时间复杂度和空间复杂度各不相同,选择时需根据数据特性与应用场景权衡。
|
6月前
|
机器学习/深度学习 算法 搜索推荐
DS:八大排序之归并排序、计数排序
DS:八大排序之归并排序、计数排序
|
6月前
|
存储 搜索推荐 测试技术
DS:八大排序之堆排序、冒泡排序、快速排序
DS:八大排序之堆排序、冒泡排序、快速排序
|
存储 搜索推荐 算法
计数排序(Counting Sort)详解
计数排序(Counting Sort)是一种非比较排序算法,其核心思想是通过计数每个元素的出现次数来进行排序,适用于整数或有限范围内的非负整数排序。这个算法的特点是速度快且稳定,适用于某些特定场景。在本文中,我们将深入探讨计数排序的原理、步骤以及性能分析。
262 1
计数排序(Counting Sort)详解
|
存储 算法 搜索推荐
python实现【计数排序】(Count Sort)
python实现【计数排序】(Count Sort)
python实现【计数排序】(Count Sort)
|
存储 搜索推荐
十大排序之Merge Sort 归并排序
十大排序之Merge Sort 归并排序
|
搜索推荐
十大排序之Heap Sort 堆排序
十大排序之Heap Sort 堆排序