`
akon405
  • 浏览: 45031 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

2012/4/3----桶排序

 
阅读更多

清明假期第一天休息,今天继续来一个算法。今天写的是桶排序的算法实现:这个算法的思想很简单,就是把待排序的数据根据一定的映射条件分布到若干的“桶”中,然后对每个“桶”中的数据进行排序,最后再把各个桶进行合并就可以得到我们排序顺序了。

下面就是具体实现过程,里面有详细的注释:

/*
 * 桶排序的java实现
 * @version 1.0 2012/4/3
 * @author akon
 */
package com.akon405.www;
public class BucketSort {
	public BucketSort(int[] A,int length,int digit){
		int[][] B=new int[10][length];
		int[] cout=new int[10];
		int i;
		int j;
		//构造一个二维数组B,用来存放A中的数据,这里的B相当于很多桶,B[i][]代表第i个桶
		for(i=0;i<length;i++){
			B[A[i]/10][cout[A[i]/10]]=A[i];//B[0][]中存放A中进行A[i]/10运算后高位为0的数据,同理B[1][]存放高位为1的数据
			cout[A[i]/10]++;//用来计数二维数组中列中数据的个数,也就是桶A[i]中存放数据的个数
		}
		
		//下面使用直接插入排序对这个二维数组进行排序,也就是对每个桶进行排序
		for(i=0;i<10;i++){
			//下面是对具有数据的一列进行直接插入排序,也就是对B[i][]这个桶中的数据进行排序
			if(cout[i]!=0){
				for(j=0;j<cout[i];j++){
					int key=B[i][j];
					int n=j-1;
					while(n>=0&&B[i][j]<B[i][j-1]){
						B[i][j]=B[i][j-1];//向前移动一位,直到key>B[i][j-1]或者确定key为最小值的时候才结束
						j--;
					}
					B[i][j]=key;
				}
			}
		}
		
		//打印输出这个二维数组,就可以得到排序过后的顺序
		for(i=0;i<10;i++){
			if(cout[i]!=0){
				for(j=0;j<cout[i];j++){
					System.out.println(B[i][j]+",");
				}
					
			}
			
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A={1,5,2,10,65,23,31};
		int length=A.length;
		int digit=10;//最大位数,这里为十位,它的作用是在向桶存放数据的时候构造一个映射,这里的映射条件是A[i]/digit
		new BucketSort(A,length,10);
	}

}
 
0
0
分享到:
评论

相关推荐

    java算法——基数排序/桶排序

    基数排序/桶排序 *统计将数组中的数字分配到桶中后,各个桶中的数字个数 *数组中每个数的每一位数根据大小分配到对应大小为0~9的桶 *将各个桶中的数字个数,转化成各个桶中最后一个数字的下标索引

    桶排序-解决排序问题

    桶排序(Bucket Sort)是一种分布式排序算法,常用于大数据处理和流式计算中。它将待排序的数据分布到多个“桶”中,每个桶再独立地进行排序,最后按照桶的顺序依次取出桶中的元素,形成有序序列。桶排序的核心思想...

    poi全家桶ooxml-schemas/poi/poi-examples/poi-ooxml/poi-ooxml-schemas/poi-scratchpad

    标题中的"poi全家桶ooxml-schemas/poi/poi-examples/poi-ooxml/poi-ooxml-schemas/poi-scratchpad"提及的是Apache POI项目中的多个关键组件和目录结构。Apache POI是一个开源的Java库,专门用于读写Microsoft Office...

    第3课 桶排序.pdf--

    3. **数组模拟桶的过程**:在C++中,数组可以用来模拟桶排序中的桶。数组的下标代表桶的编号,而下标对应的值代表桶内元素的数量。对于给定的整数序列,我们可以利用数组来记录每个整数出现的次数。 4. **处理重复...

    排序算法-桶排序

    3. **桶内排序**:对每个非空桶进行排序,这里可以使用其他的排序算法,如插入排序、快速排序等。如果桶内元素数量较少,简单的排序算法可能更高效。 4. **收集结果**:按照桶的顺序依次处理每个桶中的数据,将其按...

    算法-理论基础- 排序- 桶排序(包含源程序).rar

    3. **桶内排序**:对每个非空的桶进行排序,可以采用其他排序算法,如插入排序、快速排序等。对于小规模数据或几乎有序的数据,可以选择简单排序算法;对于大规模数据,可以考虑更高效的算法。 4. **收集结果**:...

    详解Java常用排序算法-桶排序

    4. 然后,对每个桶中的元素进行排序。 5. 最后,将所有桶中的元素取出来,组成有序的数组。 在上面的代码中,`bucketSort` 函数接受一个整数数组和桶的大小作为输入,并使用桶排序算法对该数组进行排序。该函数首先...

    桶排序 c++实现

    3. **对每个桶进行排序**:每个桶内部的数据可以用其他排序算法(如快速排序、归并排序或插入排序)进行排序。对于小规模数据,选择简单排序算法可能更高效。 4. **收集结果**:按照顺序依次处理每个非空桶,将桶中...

    用Java实现桶排序

    ### 使用Java实现桶排序 #### 知识点概述 桶排序是一种分布式的排序算法,它将数组分到有限数量的“桶”里,然后分别对每个桶进行排序(通常是使用其他排序算法)。最后,将各个桶的数据按顺序合并起来得到最终...

    spring-boot示例项目

    config(配置中心)、cloud-gateway(服务网关)、email(邮件发送)、cloud-alibaba(微服务全家桶)等模块 ### 开发环境 - JDK1.8 + - Maven 3.5 + - IntelliJ IDEA ULTIMATE 2019.1 - MySql 5.7 + ##...

    C语言桶排序

    3. 桶内排序:对每个非空的桶,使用其他排序算法(如插入排序、快速排序等)进行内部排序。这里可以使用递归或者迭代的方式来处理。 4. 合并:按照桶的顺序依次取出每个桶中的元素,将它们按顺序合并到结果序列中。...

    桶排序算法

    3. 桶内排序:对每个非空桶进行单独排序。桶内排序可以采用其他排序算法,如插入排序、快速排序等,这取决于桶内元素的数量和特性。如果桶内元素较少,简单的排序算法可能更有效。 4. 合并结果:按照桶的顺序,依次...

    桶排序算法的c++实现

    假定:输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数基本思想将区间[0, 1)划分为n个大小相等的子区间(桶),每桶大小1/n:[0, 1/n), [1/n, 2/n), [2/n, 3/n),…,[k/n, (k+1)/n ),…将n个输入元素分配...

    桶排序算法的实现与比较

    4. 合并:按照顺序依次处理每个桶,将已排序的桶内数据合并到全局有序序列中。 快速排序,另一方面,是基于分治策略的内部排序算法,由C.A.R. Hoare在1960年提出。快速排序的基本思想是选取一个基准值,将数组分为...

    桶排序算法(C++版)

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分到几个有序的桶里,每个桶再分别排序,最后按照每个桶内元素的顺序依次取出,组合成整体的有序序列。这种算法适用于数据分布相对均匀的情况。下面...

    桶排序代码

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分布到多个“桶”中,每个桶再分别独立地进行排序,最后再按照每个桶内元素的顺序依次取出,组合成完全排序的序列。这种算法适用于数据在一定范围内...

    Java排序算法(桶排序,基数排序等)

    4. 希尔排序(Shell Sort) 希尔排序是插入排序的一种优化版本,通过将待排序的元素按照一定间隔分组,然后对每组进行插入排序,逐渐减小间隔,直到间隔为1,完成排序。希尔排序的时间复杂度取决于间隔序列的选择,...

    桶排序的时间复杂度的计算公式.docx

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分布到有限数量的桶里,每个桶再分别进行排序,最后将所有桶中的数据合并,得到全局有序的结果。桶排序的时间复杂度分析是理解其效率的关键部分。下面...

    桶排序_BUCKETSORT

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分布到多个“桶”中,每个桶再分别独立地进行排序,最后按照每个桶内排序好的结果依次取出,组合成整个序列的有序排列。这种算法的核心思想是将数据...

    Python3实现桶排序(源代码)

    ### Python3实现桶排序(源代码)的知识点详解 #### 一、桶排序的基本概念与原理 桶排序(Bucket Sort)是一种高效的排序算法,尤其在处理具有特定分布规律的数据时表现突出。它属于非比较型排序算法之一,通过将...

Global site tag (gtag.js) - Google Analytics