[数据结构与算法] Java实现计数排序

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Java实现计数排序 -> 正文阅读

[数据结构与算法]Java实现计数排序

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）

代码

实现计数排序（非比较排序，牺牲空间弥补时间）
1. 优点：比较快，通常快于其它排序算法
2. 缺点：需要知道元素范围,并且元素的范围不能太大，否者失去优点
注：计数排序是需要获取数组的最大值和最小值，假如条件没给出，可能还需要自己写个循环，里面同时比较最大和最小，然后才能知道存储计数的数组的大小
注：我这里以0-100的数为例 max - min +1

public static void main(String[] args) {
        int[] arr = {1,2,5,2,7,99,4};
        System.out.println("计数排序前" + Arrays.toString(arr));
        countingSort(arr);
        System.out.println("计数排序后" + Arrays.toString(arr));

    }

    public static  void countingSort(int[] arr) {
        int[] temp = new int[101];
        // 计数
        for (int i = 0; i < arr.length; i++) {
            temp[arr[i]]++;
        }
        // 将临时数组中数据依次放回原数组
        int index = 0;
        for (int i = 0; i < temp.length; i++) {
            // 多个数的话，index++
            while (temp[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }