Java 十大排序算法之计数排序刨析

计数排序是非比较的排序算法，用辅助数组对数组中出现的数字计数，元素转下标，下标转元素

计数排序优缺点

优点：快

缺点：数据范围很大，比较稀疏，会导致辅助空间很大，造成空间的浪费

使用范围：数据较为密集或范围较小时适用。

思路

1.找出最大元素max

2.初始化一个max+1的数组

3.将每个元素的计数存储在数组中各自的索引处

4.存储计数数组元素的累积和

5.数组中找到原始数组的每个元素的索引

计数排序代码实现

public class CountingSort {
    private static int[] countingSort(int[] arr) {
        //1、求取最大值和最小值，计算中间数组的长度：中间数组是用来记录原始数据中每个值出现的频率
        int min = arr[0], max = arr[0];
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }

        //2、有了最大值和最小值能够确定中间数组的长度
        //例如存储 5-0+1=6
        int[] countArray = new int[max - min + 1];

        //3、循环遍历旧数组计数排序: 就是统计原始数组值出现的频率到中间数组B中
        for (int i : arr) {
            countArray[i - min] += 1; //数的位置上+1
        }

        //4、统计数组做变形，后边的元素等于前面的元素之和
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        //5、倒序遍历原始数组，从统计数组中找到正确的位置，输出到结果数组
        int[] resultArray = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            //给resultArray的当前位置赋值
            resultArray[countArray[arr[i] - min] - 1] = arr[i];
            //给countArray的位置的值--
            countArray[arr[i] - min]--;
        }
        return resultArray;
    }

    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        int[] sortedArr = countingSort(arr);
        System.out.println(Arrays.toString(sortedArr));
    }
}

时间复杂度：O(n+k)

到此这篇关于Java 十大排序算法之计数排序刨析的文章就介绍到这了,更多相关Java 计数排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java 十大排序算法之冒泡排序刨析

    Java 十大排序算法之冒泡排序刨析

    目录 冒泡排序原理 冒泡排序API设计 冒泡排序的代码实现 冒泡排序的时间复杂度分析 冒泡排序原理 ①比较相邻的元素,如果前一个元素比后一个元素大,则交换这两个元素的位置 ②对每一对相邻的元素循环上面的步骤,最终最后面的元素就是最大值 冒泡排序API设计 类名 Bubble 构造方法 Bubble:创建Bubble对象 成员方法 1.public static void sort(Comparable[] a):对数组内元素进行排序 2.private static void greater(C

  • java 排序算法之归并排序

    java 排序算法之归并排序

    目录 简单介绍 基本思想 思路分析 代码实现 对代码的一些改进 大数据量耗时测试 复杂度 简单介绍 归并排序(merge sort)是利用 归并 的思想实现的排序方法,该算法采用经典的 分治(divide-and-conquer)策略 : 分(divide):将问题分成一些小的问题,然后递归求解 治(conquer):将分的阶段得到的各答案「修补」在一起 即:分而治之 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使

  • java 排序算法之冒泡排序

    java 排序算法之冒泡排序

    目录 基本介绍 图解冒泡排序算法的过程 代码实现 演变过程 优化 封装算法 大量数据耗时测试 基本介绍 冒泡排序(Bubble Sorting)(时间复杂度为 O(n²))的基本思想:通过对待排序序列 从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就像水底下的旗袍一样逐渐向上冒. 优化点:因为排序过程中,个元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志判断元素是否进行过交换.从而减

  • java 排序算法之选择排序

    java 排序算法之选择排序

    目录 基本介绍 基本思想 思路分析 代码实现 演变过程 优化 算法函数封装 大量数据耗时测试 基本介绍 选择排序(select sorting)也属于内部排序法,是从欲排序的数据中,按指定的规则选出来某个元素,再依规定交换位置后达到排序的目的. 它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 基本思想 选择排序(select sorting)也是一种简单直

  • Java 十大排序算法之插入排序刨析

    Java 十大排序算法之插入排序刨析

    目录 插入排序原理 插入排序API设计 插入排序代码实现 插入排序的时间复杂度分析 插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位 插入排序API设计 类名 Insertion 构造方法 Insertion():创建Insertion对象 成员方法 1.public static void sort

  • Java 十大排序算法之归并排序刨析

    目录 归并排序原理 归并排序API设计 归并排序代码实现 归并排序的时间复杂度分析 归并排序原理 1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止. ⒉将相邻的两个子组进行合并成一个有序的大组. 3.不断的重复步骤2,直到最终只有一个组为止. 归并排序API设计 类名 Merge 构造方法 Merge():创建Merge对象 成员方法 1.public static void sort(Comparable[] a):对数组内的元素进行

  • java 排序算法之快速排序

    java 排序算法之快速排序

    目录 简单介绍 基本思想 思路分析 代码实现 推导实现 完整实现 大数据量耗时测试 性能分析 简单介绍 快速排序(Quicksort) 是对 冒泡排序的一种改进. 基本思想 快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定一个分界值(基准值),通过该分界值将数组分成左右两部分. (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边.此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值. (3)然后,左边和右边的数据可以

  • Java 十大排序算法之选择排序刨析

    Java 十大排序算法之选择排序刨析

    目录 选择排序原理 选择排序API设计 选择排序代码实现 选择排序的时间复杂度 选择排序原理 ①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后找到最小值所在的索引 ②交换第一个索引处和最小值所在的索引处的值 选择排序API设计 类名 Selection 构造方法 Selection():创建Selection对象 成员方法 1.public static void sort(Comparable[] a):对

  • Java十大经典排序算法图解

    Java十大经典排序算法图解

    目录 0.算法概述 0.1 算法分类 0.2 算法复杂度 0.3 相关概念 1.冒泡排序(Bubble Sort) 1.1 算法描述 1.2 动图演示 1.3 代码实现 2.选择排序(Selection Sort) 2.1 算法描述 2.2 动图演示 2.3 代码实现 2.4 算法分析 3.插入排序(Insertion Sort) 3.1 算法描述 3.2 动图演示 3.3代码实现 3.4 算法分析 4.希尔排序(Shell Sort) 4.1 算法描述 4.2 动图演示 4.3 代码实现 4.

  • Java 十大排序算法之希尔排序刨析

    Java 十大排序算法之希尔排序刨析

    目录 希尔排序原理 希尔排序的API设计 希尔排序的代码实现 希尔排序是插入排序的一种,又称"缩小增量排序",是插入排序算法的一种更高效的改进版本. 希尔排序原理 1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组. 2.对分好组的每一组数据完成插入排序. 3.减小增长量,最小减为1,重复第二步操作. 希尔排序的API设计 类名 Shell 构造方法 Shell():创建Shell对象 成员方法 1.public static void sort(Comparable

随机推荐