计数排序和桶排序(Java实现)

时间:2022-02-01 09:06:19

目录

  1. 计数排序适用数据范围
  2. 过程分析
  1. 网络流传桶排序算法勘误
  2. 桶排序适用数据范围
  3. 过程分析

比较和非比较的区别

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。

冒泡排序之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均O(nlogn)

比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。

计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr[i]之前有多少个元素,则唯一确定了arr[i]在排序后数组中的位置。

非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度O(n)

非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

计数排序

计数排序适用数据范围

计数排序需要占用大量空间,它仅适用于数据比较集中的情况。比如 [0100],[1000019999] 这样的数据。

过程分析

计数排序的基本思想是:对每一个输入的元素arr[i],确定小于 arr[i] 的元素个数

所以可以直接把 arr[i] 放到它输出数组中的位置上。假设有5个数小于 arr[i],所以 arr[i] 应该放在数组的第6个位置上。

下面给出两种实现:

算法流程(1)

需要三个数组:

待排序数组 int[] arr = new int[]{4,3,6,3,5,1};

辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1

输出数组 int[] res = new int[arr.length];

1.求出待排序数组的最大值max=6, 最小值min=1

2.实例化辅助计数数组help,help数组中每个下标对应arr中的一个元素,help用来记录每个元素出现的次数

3.计算 arr 中每个元素在help中的位置 position = arr[i] - min,此时 help = [1,0,2,1,1,1]; (3出现了两次,2未出现)

4.根据 help 数组求得排序后的数组,此时 res = [1,3,3,4,5,6]

public static int[] countSort1(int[] arr){
if (arr == null || arr.length == 0) {
return null;
} int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE; //找出数组中的最大最小值
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
} int help[] = new int[max]; //找出每个数字出现的次数
for(int i = 0; i < arr.length; i++){
int mapPos = arr[i] - min;
help[mapPos]++;
} int index = 0;
for(int i = 0; i < help.length; i++){
while(help[i]-- > 0){
arr[index++] = i+min;
}
} return arr;
}
算法流程(2)

需要三个数组:

待排序数组 int[] arr = new int[]{4,3,6,3,5,1};

辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1

输出数组 int[] res = new int[arr.length];

1.求出待排序数组的最大值max=6, 最小值min=1

2.实例化辅助计数数组help,help用来记录每个元素之前出现的元素个数

3.计算 arr 每个数字应该在排序后数组中应该处于的位置,此时 help = [1,1,4,5,6,7];

4.根据 help 数组求得排序后的数组,此时 res = [1,3,3,4,5,6]

public static int[] countSort2(int[] arr){
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE; //找出数组中的最大最小值
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
} int[] help = new int[max - min + 1]; //找出每个数字出现的次数
for(int i = 0; i < arr.length; i++){
int mapPos = arr[i] - min;
help[mapPos]++;
} //计算每个数字应该在排序后数组中应该处于的位置
for(int i = 1; i < help.length; i++){
help[i] = help[i-1] + help[i];
} //根据help数组进行排序
int res[] = new int[arr.length];
for(int i = 0; i < arr.length; i++){
int post = --help[arr[i] - min];
res[post] = arr[i];
} return res;
}

桶排序

网络流传桶排序算法勘误

网络各博文中流程的桶排序算法实际上都是计数排序,并非标准的桶排序。有问题的文章:

经典排序算法 - 桶排序Bucket sort

桶排序算法

排序算法 之 桶排序

最快最简单的排序算法:桶排序

桶排序适用数据范围

桶排序可用于最大最小值相差较大的数据情况,比如[9012,19702,39867,68957,83556,102456]。

但桶排序要求数据的分布必须均匀,否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。

过程分析

桶排序的基本思想是:把数组 arr 划分为n个大小相同子区间(桶),每个子区间各自排序,最后合并

计数排序是桶排序的一种特殊情况,可以把计数排序当成每个桶里只有一个元素的情况。

1.找出待排序数组中的最大值max、最小值min

2.我们使用 动态数组ArrayList 作为桶,桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1

3.遍历数组 arr,计算每个元素 arr[i] 放的桶

4.每个桶各自排序

5.遍历桶数组,把排序好的元素放进输出数组

public static void bucketSort(int[] arr){

    int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
} //桶数
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
} //将每个元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
} //对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
} System.out.println(bucketArr.toString()); }

计数排序和桶排序(Java实现)的更多相关文章

  1. 计数排序与桶排序python实现

    计数排序与桶排序python实现 计数排序 计数排序原理: 找到给定序列的最小值与最大值 创建一个长度为最大值-最小值+1的数组,初始化都为0 然后遍历原序列,并为数组中索引为当前值-最小值的值+1 ...

  2. 计数排序与桶排序&lpar;bucket sort&rpar;

    Bucket Sort is a sorting method that subdivides the given data into various buckets depending on cer ...

  3. 计数排序、桶排序python实现

    计数排序在输入n个0到k之间的整数时,时间复杂度最好情况下为O(n+k),最坏情况下为O(n+k),平均情况为O(n+k),空间复杂度为O(n+k),计数排序是稳定的排序. 桶排序在输入N个数据有M个 ...

  4. 线性时间的排序算法--桶排序&lpar;以leetcode164&period; Maximum Gap为例讲解&rpar;

    前言 在比较排序的算法中,快速排序的性能最佳,时间复杂度是O(N*logN).因此,在使用比较排序时,时间复杂度的下限就是O(N*logN).而桶排序的时间复杂度是O(N+C),因为它的实现并不是基于 ...

  5. 【JS面试向】选择排序、桶排序、冒泡排序和快速排序简介

    新年伊始,又到了金三银四的时候了.面对前端越来越多的算法面试题,我简单的整理了一下几种比较常见的数组排序方式,分别介绍其基本原理和优劣势.(ps:才疏学浅,希望大家可以在issues下面指出问题) 选 ...

  6. 使用 js 实现十大排序算法&colon; 桶排序

    使用 js 实现十大排序算法: 桶排序 桶排序 refs xgqfrms 2012-2020 www.cnblogs.com 发布文章使用:只允许注册用户才可以访问!

  7. 排序基础之非比较的计数排序、桶排序、基数排序&lpar;Java实现&rpar;

    转载请注明原文地址: http://www.cnblogs.com/ygj0930/p/6639353.html  比较和非比较排序 快速排序.归并排序.堆排序.冒泡排序等比较排序,每个数都必须和其他 ...

  8. 排序算法-桶排序(Java)

    package com.rao.sort; import java.util.*; /** * @author Srao * @className BucketSort * @date 2019/12 ...

  9. Java排序算法——桶排序

    文字部分为转载:http://hxraid.iteye.com/blog/647759 对N个关键字进行桶排序的时间复杂度分为两个部分: (1) 循环计算每个关键字的桶映射函数,这个时间复杂度是O(N ...

随机推荐

  1. Unity Animation System(动画系统)

    动画系统: 支持:动画融合,混合,叠加动画,行走循环的时间同步,动画层,控制动画的各个方面(时间,速度,融合权重)   带有每顶点1.2或4骨骼的蒙皮网格,以及支持基于物理的布娃娃系统和程序动画.   ...

  2. vs2005升级到vs2010相关问题

    1.项目编译失败,报 Resgen.exe 退出 ,错误代码2 处理方式: http://jingyan.baidu.com/article/90895e0fe80c6064ed6b0b6b.html ...

  3. Linux系统维护修复模式

    基于PXE方式的Linux系统维护工具箱     在安装RedHat Linux系统的过程中,我们知道可以通过PXE方式进行安装,从而解决了无光驱或无安装介质(光盘)来安装操作系统.但是当系统由于某种 ...

  4. &grave;DevOps&grave;相关知识搜集

    本文记录的是搞清楚什么是DevOps过程中检索资料时发现的有价值的帖子. 传送门: 我眼中的DevOps 作者简介:申思维,2005年本科毕业于华南理工大学计算机学院.一直从事Web领域的开发,3年多 ...

  5. leetcode3:无重复字符的最长子串

    给定一个字符串,找出不含有重复字符的最长子串的长度. 示例: 给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3. 给定 &q ...

  6. spark提示Caused by&colon; java&period;lang&period;ClassCastException&colon; scala&period;collection&period;mutable&period;WrappedArray&dollar;ofRef cannot be cast to &lbrack;Lscala&period;collection&period;immutable&period;Map&semi;

    spark提示Caused by: java.lang.ClassCastException: scala.collection.mutable.WrappedArray$ofRef cannot b ...

  7. linux启动

    启动顺序:POST加电自检——加载BIOS——读取MBR——GRUB引导——加载kernel——rc0~rc6级别启动——加载内核模块——加载rc.sysinit——inittab运行级别——读取rc ...

  8. Javascript中的this对象

    对于this的使用,我们最常遇到的主要有,在全局函数中,在对象方法中,call和apply时,闭包中,箭头函数中以及class中: 我们知道this对象是在运行时基于函数的执行环境绑定的,在调用函数之 ...

  9. spark单机模式

    1.下载spark,解压2.复制conf/spark-env.sh和conf/log4j.properties cp spark-env.sh.template spark-env.sh cp log ...

  10. git工程迁移&lpar;修改提交服务器地址&rpar;方法

    git remote set-url [--push] <name> <newurl> [<oldurl>]git remote set-url --add [-- ...