java数据结构与算法之桶排序实现方法详解

本文实例讲述了java数据结构与算法之桶排序实现方法。分享给大家供大家参考,具体如下:

基本思想:

假定输入是由一个随机过程产生的[0, M)区间上均匀分布的实数。将区间[0, M)划分为n个大小相等的子区间(桶),将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <M辅助数组B[0..n-1]是一指针数组,指向桶(链表)。将n个记录分布到各个桶中去。如果有多于一个记录分到同一个桶中,需要进行桶内排序。最后依次把各个桶中的记录列出来记得到有序序列。

[桶——关键字]映射函数

bindex=f(key)   其中,bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效,其关键在于这个映射函数,它必须做到:如果关键字k1<k2,那么f(k1)<=f(k2)。也就是说B(i)中的最大数据都要小于B(i+1)中最小数据。很显然,映射函数的确定与数据本身的特点有很大的关系,我们下面举个例子:

假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶,然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中,并在每个非空的桶中进行快速排序后得到如下图所示:

对上图只要顺序输出每个B[i]中的数据就可以得到有序序列了。

算法核心代码如下:

/// <summary>
/// 桶排序
///
///如果有重复的数字,则需要 List<int>数组,这里举的例子没有重复的数字
/// </summary>
/// <param name="unsorted">待排数组</param>
/// <param name="maxNumber">待排数组中的最大数,如果可以提供的话</param>
/// <returns></returns>
static int[] bucket_sort(int[] unsorted, int maxNumber = 97)
{
 int[] sorted = new int[maxNumber + 1];
 for (int i = 0; i < unsorted.Length; i++)
 {
  sorted[unsorted[i]] = unsorted[i];
 }
 return sorted;
}
static void Main(string[] args)
{
 int[] x = {49、 38 、 35、 97 、 76、 73 、 27、 49 };
 var sorted = bucket_sort(x, 97);
 for (int i = 0; i < sorted.Length; i++)
 {
  if (sorted[i] > 0)
   Console.WriteLine(sorted[i]);
 }
 Console.ReadLine();
}

桶排序代价分析

桶排序利用函数的映射关系,减少了几乎所有的比较工作。实际上,桶排序的f(k)值的计算,其作用就相当于快排中划分,已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

对N个关键字进行桶排序的时间复杂度分为两个部分:

(1) 循环计算每个关键字的桶映射函数,这个时间复杂度是O(N)。
(2) 利用先进的比较排序算法对每个桶内的所有数据进行排序,其时间复杂度为  ∑ O(Ni*logNi) 。其中Ni 为第i个桶的数据量。

很显然,第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此,我们需要尽量做到下面两点:

(1) 映射函数f(k)能够将N个数据平均的分配到M个桶中,这样每个桶就有[N/M]个数据量。
(2) 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据,这样就完全避开了桶内数据的“比较”排序操作。当然,做到这一点很不容易,数据量巨大的情况下,f(k)函数会使得桶集合的数量巨大,空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

对于N个待排数据,M个桶,平均每个桶[N/M]个数据的桶排序平均时间复杂度为:

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

当N=M时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

总结: 桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。此外,桶排序是稳定的。

即以下三点:

1. 桶排序是稳定的
2. 桶排序是常见排序里最快的一种,比快排还要快…大多数情况下
3. 桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法

补充:在查找算法中,基于比较的查找算法最好的时间复杂度也是O(logN)。比如折半查找、平衡二叉树、红黑树等。但是Hash表却有O(C)线性级别的查找效率(不冲突情况下查找效率达到O(1))。那么:Hash表的思想和桶排序是不是有一曲同工之妙呢?

实际上,桶排序对数据的条件有特殊要求,如果数组很大的话,那么分配几亿个桶显然是不可能的。所以桶排序有其局限性,适合元素值集合并不大的情况。

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

时间: 2017-05-01

详解java数据结构与算法之双链表设计与实现

在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因

java数据结构排序算法之归并排序详解

本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

Java常见数据结构面试题(带答案)

1.栈和队列的共同特点是(只允许在端点处插入和删除元素) 4.栈通常采用的两种存储结构是(线性存储结构和链表存储结构) 5.下列关于栈的叙述正确的是(D)      A.栈是非线性结构B.栈是一种树状结构C.栈具有先进先出的特征D.栈有后进先出的特征 6.链表不具有的特点是(B)A.不必事先估计存储空间       B.可随机访问任一元素 C.插入删除不需要移动元素      D.所需空间与线性表长度成正比 7.用链表表示线性表的优点是(便于插入和删除操作) 8.在单链表中,增加头结点的目的是(

java 数据结构之栈与队列

java 数据结构之栈与队列 一:对列 队列是一种先进先出的数据结构 实现代码: package Queue; /* * 使用java构建队列,并模拟实现队列的入队和出对方法 */ public class Queue { //队列类 private int maxSize; //定义队列的长度 private int[] arrQueue; //队列 private int rear; //定义队列的尾指针 private int front; //定义队列的头指针 private int e

java数据结构与算法之插入排序详解

本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键

浅析Java 数据结构常用接口与类

Java工具包提供了强大的数据结构.在Java中的数据结构主要包括以下几种接口和类: 枚举(Enumeration) 位集合(BitSet) 向量(Vector) 栈(Stack) 字典(Dictionary) 哈希表(Hashtable) 属性(Properties) 以上这些类是传统遗留的,在Java2中引入了一种新的框架-集合框架(Collection),我们后面再讨论. 枚举(Enumeration) 枚举(Enumeration)接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里

浅析Java中comparator接口与Comparable接口的区别

Comparable 简介 Comparable 是排序接口. 若一个类实现了Comparable接口,就意味着"该类支持排序".  即然实现Comparable接口的类支持排序,假设现在存在"实现Comparable接口的类的对象的List列表(或数组)",则该List列表(或数组)可以通过 Collections.sort(或 Arrays.sort)进行排序. 此外,"实现Comparable接口的类的对象"可以用作"有序映射(如

java中常用工具类之字符串操作类和MD5加密解密类

java中常用的工具类之String和MD5加密解密类 我们java程序员在开发项目的是常常会用到一些工具类.今天我分享一下我的两个工具类,大家可以在项目中使用. 一.String工具类 package com.itjh.javaUtil; import java.io.ByteArrayInputStream; import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import

浅析Java类和数据结构中常用的方法

1.Object类里面常用的方法: protected Object clone()创建并返回此对象的一个副本. boolean equals(Object obj)指示其他某个对象是否与此对象"相等". protected void finalize()当垃圾回收器确定不存在对该对象的更多引用时,由对象的垃圾回收器调用此方法. Class<?> getClass()返回此 Object 的运行时类. int hashCode()返回该对象的哈希码值. void notif

浅谈Java中常用数据结构的实现类 Collection和Map

线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构.这些类均在java.util包中.本文试图通过简单的描述,向读者阐述各个类的作用以及如何正确使用这些类. Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ├HashMap └WeakHashMap Collection接口 Collection是最基本的集合接口,一个C

Java常用正则表达式验证类完整实例【邮箱、URL、IP、电话、身份证等】

本文实例讲述了Java常用正则表达式验证类.分享给大家供大家参考,具体如下: package com.fsti.icop.util.regexp; import java.util.regex.Matcher; import java.util.regex.Pattern; public final class RegExpValidatorUtils { /** * 验证邮箱 * * @param 待验证的字符串 * @return 如果是符合的字符串,返回 <b>true </b&g

浅析Java 常用的 4 种加密方式(MD5+Base64+SHA+BCrypt)

一.工具类  md5加密工具类  public class MD5Utils { private static final String hexDigIts[] = {"0","1","2","3","4","5","6","7","8","9","a","b",&qu

Java多态和实现接口的类的对象赋值给接口引用的方法(推荐)

接口的灵活性就在于"规定一个类必须做什么,而不管你如何做". 我们可以定义一个接口类型的引用变量来引用实现接口的类的实例,当这个引用调用方法时,它会根据实际引用的类的实例来判断具体调用哪个方法,这和上述的超类对象引用访问子类对象的机制相似. //定义接口InterA interface InterA { void fun(); } //实现接口InterA的类B class B implements InterA { public void fun() { System.out.pri

Java语言Lang包下常用的工具类介绍

无论你在开发哪中 Java 应用程序,都免不了要写很多工具类/工具函数.你可知道,有很多现成的工具类可用,并且代码质量都很不错,不用你写,不用你调试,只要你发现. 在 Apache Jakarta Common 中, Lang 这个 Java 工具包是所有 Apache Jakarta Common 项目中被使用最广泛的,几乎你所知道的名气比较大的软件里面都有用到它,包括 Tomcat, Weblogic, Websphere, Eclipse 等等.我们就从这个包开始介绍整个 common 项

Java NIO Path接口和Files类配合操作文件的实例

Path接口 1.Path表示的是一个目录名序列,其后还可以跟着一个文件名,路径中第一个部件是根部件时就是绝对路径,例如 / 或 C:\ ,而允许访问的根部件取决于文件系统: 2.以根部件开始的路径是绝对路径,否则就是相对路径: 3.静态的Paths.get方法接受一个或多个字符串,字符串之间自动使用默认文件系统的路径分隔符连接起来(Unix是 /,Windows是 \ ),这就解决了跨平台的问题,接着解析连接起来的结果,如果不是合法路径就抛出InvalidPathException异常,否则就