桶排序（Bucket Sort）
前面介紹了9種不同的排序算法痹束，那現(xiàn)在就直接來看以下桶排序的執(zhí)行流程
- 創(chuàng)建一定數(shù)量的桶（比如用數(shù)組检疫，鏈表作為桶）
- 按照一定的規(guī)則（不同類型的數(shù)據(jù)，規(guī)則不同）祷嘶，將序列中的元素均勻分配到對(duì)應(yīng)的桶
- 分別對(duì)每個(gè)桶進(jìn)行單獨(dú)排序
- 將所有非空桶的元素合并成有序序列
例如現(xiàn)在需要對(duì)下圖中的小數(shù)進(jìn)行排序
由于現(xiàn)在有8個(gè)元素屎媳，就可以創(chuàng)建8個(gè)桶，每個(gè)桶都是一個(gè)數(shù)組论巍，然后利用元素值 * 待排序元素?cái)?shù)量 得到每一個(gè)元素的索引
然后再對(duì)每個(gè)桶進(jìn)行單獨(dú)排序烛谊，最終每個(gè)桶排序后的結(jié)果為
.png
然后再將非空桶中的元素進(jìn)行合并，最終合并后的結(jié)果為
所以嘉汰，基于小數(shù)的桶排序算法如下
protected void sort() {
List<Double>[] buckets = new List[array.length];
for (int i = 0; i < array.length; i++) {
int bucketIndex = (int)(array[i] * array.length);
List<Double> bucket = buckets[bucketIndex];
if (bucket == null) {
bucket = new LinkedList<>();
buckets[bucketIndex] = bucket;
}
bucket.add(array[i]);
}
int index = 0;
for (int i = 0; i < buckets.length; i++) {
if (buckets[i] == null) continue;
buckets[i].sort(null);
for (Double d :
buckets[i]) {
array[index++] = d;
}
}
System.out.println(array);
}
需要注意丹禀，不同的數(shù)據(jù)類型，桶排序的實(shí)現(xiàn)是不一樣的鞋怀，所以無法給出統(tǒng)一的算法双泪。可以作為一種思路來進(jìn)行了解接箫。
完攒读！
