首页 > 代码库 > 桶排序
桶排序
参考资料：算法导论
note1:桶排序是另外一种以O(n)或者接近O(n)的复杂度排序的算法. 它假设输入的待排序元素是等可能的落在等间隔的值区间内.一个长度为N的数组使用桶排序, 需要长度为N的辅助数组. 等间隔的区间称为桶, 每个桶内落在该区间的元素. 桶排序是基数排序的一种归纳结果
note2:待排序元素越均匀, 桶排序的效率越高. 均匀意味着每个桶在中间过程中容纳的元素个数都差不多,不会出现特别少或者特别多的情况, 这样在排序子程序进行桶内排序的过程中会达到最优效率.
note3:将元素通过恰当的映射关系将元素尽量等数量的分到各个桶(值区间)里面, 这个映射关系就是桶排序算法的关键.桶的标记(数组索引Index)的大小也要和值区间有对应关系
代码：
1 package sorts; 2 3 import java.util.Arrays; 4 import java.util.Random; 5 6 class Bucket { 7 private double data; 8 private Bucket next; 9 public double getData() {10 return data;11 }12 public void setData(double data) {13 this.data =http://www.mamicode.com/ data;14 }15 public Bucket getNext() {16 return next;17 }18 public void setNext(Bucket next) {19 this.next = next;20 }21 @Override22 public String toString() {23 return Double.toString(data);24 }25 }26 27 public class BucketSort {28 29 /**30 * Input element MUST be in the range [0, 1). Or31 * the program may not function properly.32 * */33 public static void sort(double[] a) {34 // init35 Bucket[] buckets = new Bucket[a.length];36 int n = a.length;37 // sort38 for (int i = 0; i < a.length; i++) {39 addBucket(buckets, (int)(a[i] * n), a[i]);40 }41 retrieveBuckets(buckets, a);42 }43 44 private static void retrieveBuckets(Bucket[] buckets, double[] a) {45 Bucket iterator = null;46 int index = 0;47 for (int i = 0; i < buckets.length; i++) {48 iterator = buckets[i];49 while (iterator!=null) {50 a[index++] = iterator.getData();51 iterator = iterator.getNext();52 }53 }54 }55 56 // no need for insertion sort57 private static void addBucket(Bucket[] buckets, int index, double data) {58 Bucket iterator = buckets[index];59 if (iterator == null) {60 Bucket tmp = new Bucket();61 tmp.setData(data);62 tmp.setNext(buckets[index]);63 buckets[index] = tmp;64 } else {65 Bucket tmp = new Bucket();66 Bucket previous = iterator;67 tmp.setData(data);68 while ((iterator!=null) && 69 (data > iterator.getData())) {70 previous = iterator;71 iterator = iterator.getNext();72 }73 if (iterator==previous) {74 tmp.setNext(iterator.getNext());75 iterator.setNext(tmp);76 } else {77 previous.setNext(tmp);78 tmp.setNext(iterator);79 }80 }81 }82 83 // test84 public static void main(String[] args) {85 Random random = new Random();86 int num = 10;87 double[] a = new double[num];88 for (int i = 0; i < num; i++) {89 a[i] = random.nextDouble();90 }91 BucketSort.sort(a);92 System.out.println(Arrays.toString(a));93 }94 95 }
桶排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。