Java排序之计数排序

wind3110991 发布于2019-08-15 18:07 / 3204人阅读

摘要：排序之计数排序计数排序思路计数排序适用于有明确范围的数组，比如给定一个数组，且知道所有值得范围是。这个时候可以使用一个长度的数组，待排序的数组就可以散在这个数组上，数组的值就是当前值的个数，再经过一次遍历展开，得到的数组就有序了。

Java排序之计数排序 1. 计数排序思路

计数排序适用于有明确范围的数组，比如给定一个数组，且知道所有值得范围是[m,n]。这个时候可以使用一个n-m+1长度的数组，待排序的数组就可以散在这个数组上，数组的值就是当前值的个数，再经过一次遍历展开，得到的数组就有序了。

新建一个长度为n-m+1的临时数组

遍历待排序数组，它的值-m作为临时数组下角标，这个位置的值加1

遍历结束，临时数组就存储了每个值得个数

最后将它展开赋值给原数组

2. Java代码实现

package com.wangjun.arithmetic;

import java.util.Arrays;

public class SortCount {

    public static void main(String[] args) {
        //测试
        int[] arr = {1,4,6,7,5,4,3,2,1,4,5,10,9,10,3};
        sortCount(arr, 1, 10);
        System.out.println(Arrays.toString(arr));
    }
    
    //计数排序的初步实现，使用了多余的空间，可以尝试不使用多余的空间
    public static void sortCount(int[] arr, int m, int n) {
        int len = arr.length;
        int[] tem = new int[n - m + 1];
        for(int i = 0; i < len; i++) {
            tem[arr[i] - m] += 1;
        }
        for(int i = 0, index = 0; i < tem.length; i++) {
            int item = tem[i];
            while(item-- != 0) {
                arr[index++] = i + m;
            }
        }
    }

}

打印结果：

[1, 1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 9, 10, 10]

GPU云服务器云服务器计数排序 java 排序 java 排序动画 java 排序速度

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69635.html

基本算法学习(四)之计数排序(JS)

摘要：计数排序首先我们要对计数排序有一个正确的认识计数排序是用于确定范围的整数的线性时间排序算法这一句话我们就可以知道计数排序该如何用了处理数据确定范围内的整数特点快线性时间其数据如下最佳情况最差情况平均情况计数排序的步骤如下查找待排序数组中最大计数排序首先我们要对计数排序有一个正确的认识,计数排序是用于确定范围的整数的线性时间排序算法,这一句话我们就可以知道计数排序该如何用了.处理数据...

AlexTuan 2019-08-21 11:22 评论0 收藏0
【算】计数排序和桶排序

摘要：计数排序之前接触的选择快排等算法，都是着眼于怎么更快的调整元素位置，以达到排序的目的。桶排序桶排序能解决浮点数字的问题，至于槽大嘛，依然深受其害。思路桶排序与计数排序的思路多少有些类似，有数组整装待排，还是一如既往的从小到大好了。计数排序之前接触的选择、快排等算法，都是着眼于怎么更快的调整元素位置，以达到排序的目的。而计数排序则不然，设计思路可谓另辟蹊径！思路我们对15个10以...

Yangyang 2019-08-15 15:39 评论0 收藏0
【算法】计数排序 + 各个排序算法的稳定性

摘要：将大的先放在后面，再下一次可以把相同大的放在上一次的之前，顺序改变。之前介绍的排序算法：【算法】插入排序——希尔排序+直接插入排序_Rinne’s blog-C...

不知名网友 2021-11-29 10:50 评论0 收藏0
Javag工程师成神之路（2019正式版）

摘要：结构型模式适配器模式桥接模式装饰模式组合模式外观模式享元模式代理模式。行为型模式模版方法模式命令模式迭代器模式观察者模式中介者模式备忘录模式解释器模式模式状态模式策略模式职责链模式责任链模式访问者模式。主要版本更新时间备注 v1.0 2015-08-01 首次发布 v1.1 2018-03-12 增加新技术知识、完善知识体系 v2.0 2019-02-19 结构...

Olivia 2019-08-16 15:14 评论0 收藏0
常用排序算法之JavaScript实现

摘要：代码实现六堆排序算法简介堆排序是指利用堆这种数据结构所设计的一种排序算法。九计数排序算法简介计数排序是一种稳定的排序算法。计数排序不是比较排序，排序的速度快于任何比较排序算法。赞助我以写出更好的文章，give me a cup of coffee? 2017最新最全前端面试题 1、插入排序 1）算法简介插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它...

jerry 2019-08-21 12:27 评论0 收藏0