文档章节

桶排序

黑妹妹牙膏
 黑妹妹牙膏
发布于 2014/08/19 17:40
字数 321
阅读 30
收藏 0
package com.victor.sort.algorithms;

import java.util.ArrayList;

import com.victor.sort.seeds.FewUniqueKeys;
import com.victor.sort.seeds.NearSorted;
import com.victor.sort.seeds.Random;
import com.victor.sort.seeds.Reversed;
import com.victor.sort.seeds.Seeds;

/**
 * 桶排序
 * @author 黑妹妹牙膏
 *
 */
public class Bucket extends SortAlgorithms {

	/**
	 * (non-Javadoc)
	 * @see com.victor.sort.algorithms.SortAlgorithms#_sort(java.util.ArrayList)
	 * Bucket-Sort(A)
	 * 	n<-length[A]
	 * 	for i<-1 to n
	 * 		do insert A[i] into list B[[nA[i]]]
	 * 	for i <-0 to n<-1
	 *  do sort list B[i] with insertion sort
	 *  concatenate the list B[0],B[1],...,B[n-1] together in order
	 */
	
	@SuppressWarnings("unchecked")
	@Override
	protected ArrayList<Integer> doSort(ArrayList<Integer> Alist) {
		ArrayList<Integer> a = Alist;
		int n = a.size();
		
		for(int i=(n-1)/2;i>=0;i--)
		{
			a = sink(a,i,n);
		}
		int max = a.get(0);
		int d = (max+"").length();
		int mod = 1;
		
		for(int i=1;i<d;i++)
		{
			mod = mod * 10;
		}
		
		ArrayList<Integer>[] b = new ArrayList[10];
		for(int i=0;i<b.length;i++)
		{
			b[i] = new ArrayList<Integer>();
		}
		
		for(int i=0;i<n;i++)
		{
			b[a.get(i)/mod].add(a.get(i));
		}
		
		ArrayList<Integer> result = new ArrayList<Integer>();
		Insertion is = new Insertion();
		for(int i=0;i<b.length;i++)
		{
			result.addAll(is.doSort(b[i]));
		}
		return result;
	}
	
	private ArrayList<Integer> sink(ArrayList<Integer> a,int i,int n)
	{
		//get left child
		int lc = 2 * i + 1;
		if(lc >= n) return a;
		//get right child
		int rc = lc + 1;
		//get max of left and right child
		int mc = (rc >= n) ? lc : (a.get(lc) > a.get(rc) ? lc : rc);
		// if parent > max of child then return
		if(a.get(i) >= a.get(mc)) return a;
		//swap max and parent
		int temp = a.get(i);
		a.set(i, a.get(mc));
		a.set(mc, temp);
		moveMentIncrease();
		return sink(a,mc,n);
	}

	@Override
	public String getName() {
		return "Bucket";
	}
	
	public static void main(String[] args)
	{
		Seeds seed1 = new Random();
		Seeds seed2 = new NearSorted();
		Seeds seed3 = new Reversed();
		Seeds seed4 = new FewUniqueKeys();
		SortAlgorithms SA = new Bucket();
		SA.sort(seed1,10000);
//		SA.print();
		SA.sort(seed2,10000);
		SA.sort(seed3,10000);
		SA.sort(seed4,10000);
	}

}

© 著作权归作者所有

上一篇: 计数排序
下一篇: 冒泡排序法
黑妹妹牙膏
粉丝 23
博文 35
码字总数 23081
作品 0
杭州
程序员
私信 提问
计数排序vs基数排序vs桶排序

从计数排序说起 计数排序是一种非基于元素比较的排序算法,而是将待排序数组元素转化为计数数组的索引值,从而间接使待排序数组具有顺序性。 计数排序的实现一般有两种形式:基于辅助数组和基...

超人汪小建
02/18
0
0
Elasticsearch聚合的嵌套桶如何排序

版权声明:欢迎转载,请注明出处,谢谢。 https://blog.csdn.net/boling_cavalry/article/details/89816240 关于嵌套桶 在elasticsearch的聚合查询中,经常对聚合的数据再次做聚合处理,例如...

博陵精骑
05/04
0
0
JavaScript 数据结构与算法之美 - 桶排序、计数排序、基数排序

1. 前言 算法为王。 想学好前端,先练好内功,只有内功深厚者,前端之路才会走得更远。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ,旨在入门数据结构与算法和方便...

天明夜尽
07/29
0
0
桶排序(BucketSort)

  桶排序:工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(可能在使用别的排序算法,我这里用的单向链表在放入时就排好了顺序),最后依次把各个桶中的记录列出来得到有序序列。分...

Spider&Man
2018/12/26
0
0
排序算法之桶排序的深入理解以及性能分析

前言 本文为算法分析系列博文之一,深入探究桶排序,分析各自环境下的性能,同时辅以性能分析示例加以佐证 实现思路与步骤 思路 设置固定空桶数 将数据放到对应的空桶中 将每个不为空的桶进行...

撒网要见鱼
2016/12/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【0918】正则介绍_grep

【0918】正则介绍_grep 9.1 正则介绍_grep上 9.2 grep中 9.3 grep下 一、正则介绍 正则是一串有规律的字符串,它使用单个字符串来描述或匹配一系列符合某个语法规则的字符串。 二、grep工具 ...

飞翔的竹蜻蜓
12分钟前
4
0
为什么要在网站中应用CDN加速?

1. 网页加载速度更快 在网站中使用CDN技术最直接的一个好处就是它可以加快网页的加载速度。首先,CDN加速的内容分发是基于服务器缓存的,由于CDN中缓存了不少数据,它能够给用户提供更快的页...

云漫网络Ruan
50分钟前
8
0
亚玛芬体育(Amer Sports)和信必优正式启动合作开发Movesense创新

亚玛芬体育和信必优正式启动合作开发Movesense创新,作为亚玛芬体育的完美技术搭档,信必优利用Movesense传感器技术为第三方开发移动应用和服务。 Movesense基于传感器技术和开放的API,测量...

symbiochina88
今天
4
0
创龙TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA核心板规格书

SOM-TL437xF是一款广州创龙基于TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA芯片设计的核心板,采用沉金无铅工艺的10层板设计,适用于高速数据采集和处理系统、汽车导航、工业自动化等领...

Tronlong创龙
今天
4
0
好程序员Java学习路线分享MyBatis之线程优化

  好程序员Java学习路线分享MyBatis之线程优化,我们的项目存在大量用户同时访问的情况,那么就会出现大量线程并发访问数据库,这样会带来线程同步问题,本章我们将讨论MyBatis的线程同步问...

好程序员官方
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部