一、原理

桶排序的工作原理是吧區(qū)間劃分為n個(gè)大小相同的子區(qū)間，這樣的區(qū)間稱(chēng)為桶。然后將n個(gè)輸入的數(shù)分步到各個(gè)桶中去。每個(gè)桶再個(gè)別的排序，然后按照次序吧各個(gè)桶

中的元素列出來(lái)即可。

二、時(shí)間復(fù)雜度

桶排序是一種鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序陣列內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線(xiàn)性時(shí)間(O(n))。但桶排序并不是比較排序，它不受

O(nlongn)下限的影響。

eg：對(duì)大小為[1...1000]范圍內(nèi)的n個(gè)整數(shù)A[1..n]排序。可以把桶設(shè)置為大小為10的范圍，具體而言設(shè)集合B[1]存儲(chǔ)[1..10]的整數(shù)，集合B[2]存儲(chǔ)(10..20]的整數(shù)，

i=1，2，，100.總共100個(gè)桶然后掃描A[i]，吧每個(gè)A[i]放入到對(duì)應(yīng)的B[j]中。然后再對(duì)每個(gè)桶里的數(shù)字排序。

假設(shè)有n個(gè)數(shù)字，有m個(gè)桶，如果數(shù)字是平均分布的，則每個(gè)桶里面平均有n/m個(gè)數(shù)字。如果每個(gè)桶里中的數(shù)字采用快速排序，那么整個(gè)算法的復(fù)雜度是

O(n+m*n/m*log(n/m)) = O(n+nlogn-nlogm).當(dāng)m接近n時(shí)，桶排序復(fù)雜度接近O(n)。

三、代碼

import java.util.ArrayList;

import java.util.Collections;

import java.util.Random;

import java.util.List;

public class BucketSort {

int bucketSize = 10

int arraySize = 1000;

public static void main(String[] args) {

// TODO Auto-generated method stub

BucketSort bs = new BucketSort();

int[] array = bs.getArray();

bs.bucketSort(array);

}

public int[] getArray(){

int[] arr = new int[arraySize /3];

Random r = new Random();

for(int i = 0; i < arraySize /3 ; i++)

{

arr[i] = r.nextInt(100000);

}

return arr;

}

public void bucketSort(int[] a)

{

List bucket[] = new ArrayList[bucketSize];

for(int i=0; i < a.length ; i++)

{

int temp = a[i]/10000;

if(bucket[temp] == null)

{

bucket[temp] = new

ArrayList();

}

bucket[temp].add(a[i]);

}

//對(duì)桶內(nèi)各個(gè)元素進(jìn)行排序

for(int j=0;j

{

intsertSort(bucket[j]);

printList(bucket[j]);

}

}

private void printList(List list) {

// TODO Auto-generated method stub

while(list.size()>0)

{

System.out.print(list.remove(0) +"\t");

}

}

private void intsertSort(List list) {

// TODO Auto-generated method stub

Collections.sort(list);

}

}

總結(jié)

以上是生活随笔為你收集整理的bucket java_桶排序（BucketSort）（java）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。