Java实现桶排序

绝地灬酷狼 2022-05-09 13:40 99阅读 0赞

桶排序：使用额外空间，以空间换时间思想，，因此时间复杂度为O(n+m)

1.1  基本思想

桶排序是所有排序算法中最快、也是最简单的排序算法。基本思想是在知道所有待排元素的范围后，准备和这个范围同样数量的桶，并将元素放在对应的桶中，如待排元素为｛3,1,5,9,6,5,0｝，就要准备10个桶标号为0到9（代码中对应一个数组的下标），将每个元素放入对应桶中，再将所有元素按顺序输出（代码中则按顺序将数组i下标输出arrary\[i\]次），即为\{0,1,3,5,5,6,9\}。

public class TestBucketSort {
    	private int[] bucket;
    	private int[] array;
    
    	// size是一个范围
    	public TestBucketSort(int[] array) {
    		this.array = array;
    		int max = array[0];
    		int min = array[0];
    		for(int i=0; i<array.length; ++i){
    			if(array[i]>max){
    				max = array[i];
    			}
    			if(array[i]<min){
    				min = array[i];
    			}
    		}
    		bucket = new int[max-min+1]; //算出需要开辟多少个空间
    		
    	}
    
    	public void sort() {
    		for (int i = 0; i < array.length; ++i) {
    			bucket[array[i]]++;
    		}
    	}
    
    	// 遍历桶，并得到每个桶中数n，并输出n次该桶下标
    	public void print() {
    		for (int i = 0; i < bucket.length; i++){
    			for (int j = 0; j < bucket[i]; j++){
    				System.out.println(i);
    			}
    		}	
    	}
    	
    	public static void main(String[] args) {
    		 int[] array = new int[]{3,1,5,9,6,5,0}; 
           TestBucketSort order = new TestBucketSort(array); 
           order.sort();
           order.print();
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，99人围观）

还没有评论，来说两句吧...

相关阅读

相关 java 桶排序

-------------------- java 桶排序 \\\\\\\\\\\\\\\\\\\\\\\ 桶排序

灰太狼/ 2022年11月21日 09:44/ 0 赞/ 68 阅读

相关计数排序、桶排序python实现

http://blog.csdn.net/u011608357/article/details/37725455 计数排序在输入n个0到k之间的整数时，时间

深藏阁楼爱情的钟/ 2022年07月17日 02:53/ 0 赞/ 105 阅读

相关 [排序算法]--桶排序的Java实现

> 今天在刷leetcode的时候，在41题 First Missing Positive 发现了在排序算法中还有一个桶排序，顺便做个总结。桶排序关于桶排序先做几

痛定思痛。/ 2022年07月12日 03:17/ 0 赞/ 104 阅读

相关桶排序java

桶排序把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况

骑猪看日落/ 2022年06月06日 08:07/ 0 赞/ 96 阅读

相关排序算法之桶排序及Java实现

一、排序算法的分类 1. 选择排序（[直接选择排序][Link 1]，[堆排序][Link 2]） 2. 交换排序（[冒泡排序][Link 3]，[快速排序][Lin

喜欢ヅ旅行/ 2022年05月26日 04:57/ 0 赞/ 112 阅读

相关 python 实现桶排序

前言桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使

水深无声/ 2022年05月17日 08:38/ 0 赞/ 281 阅读

相关 java实现桶排序算法

前面我们详细讲解了[桶排序算法][Link 1]，现在我们用java代码实现以下 package ttt; public class BucketS

￡神魔★判官ぃ/ 2022年05月14日 04:39/ 0 赞/ 113 阅读

相关 python实现桶排序算法

前面我们讲了[桶排序算法][Link 1]，现在我们用python代码来实践一遍 !/usr/bin/python -- coding: utf-8 --

桃扇骨/ 2022年05月14日 04:37/ 0 赞/ 280 阅读

相关 Java实现桶排序

桶排序：使用额外空间，以空间换时间思想，，因此时间复杂度为O(n+m) 1.1 基本思想桶排序是所有排序算法中最快、也是最简单的排序算法。基本思想是在知道所有待排元素的

绝地灬酷狼/ 2022年05月09日 13:40/ 0 赞/ 100 阅读

相关桶排序 python实现

1 桶排序要求： 2 有几个输入数据，要求对其进行从小到大或者从大到小进行排序 3 4 思路： 5 首先建立需

我不是女神ヾ/ 2022年03月07日 09:52/ 0 赞/ 125 阅读