轉(zhuǎn)載自??漫畫(huà)：什么是桶排序

計(jì)數(shù)排序需要根據(jù)原始數(shù)列的取值范圍，創(chuàng)建一個(gè)統(tǒng)計(jì)數(shù)組，用來(lái)統(tǒng)計(jì)原始數(shù)列中每一個(gè)可能的整數(shù)值所出現(xiàn)的次數(shù)。

原始數(shù)列中的整數(shù)值，和統(tǒng)計(jì)數(shù)組的下標(biāo)是一一對(duì)應(yīng)的，以數(shù)列的最小值作為偏移量。比如原始數(shù)列的最小值是90， 那么整數(shù)95對(duì)應(yīng)的統(tǒng)計(jì)數(shù)組下標(biāo)就是 95-90 = 5。

那么，桶排序當(dāng)中所謂的“桶”，又是什么概念呢？

每一個(gè)桶（bucket）代表一個(gè)區(qū)間范圍，里面可以承載一個(gè)或多個(gè)元素。桶排序的第一步，就是創(chuàng)建這些桶，確定每一個(gè)桶的區(qū)間范圍：

具體建立多少個(gè)桶，如何確定桶的區(qū)間范圍，有很多不同的方式。我們這里創(chuàng)建的桶數(shù)量等于原始數(shù)列的元素?cái)?shù)量，除了最后一個(gè)桶只包含數(shù)列最大值，前面各個(gè)桶的區(qū)間按照比例確定。

區(qū)間跨度 = （最大值-最小值）/ （桶的數(shù)量 - 1）

第二步，遍歷原始數(shù)列，把元素對(duì)號(hào)入座放入各個(gè)桶中：

第三步，每個(gè)桶內(nèi)部的元素分別排序（顯然，只有第一個(gè)桶需要排序）：

第四步，遍歷所有的桶，輸出所有元素：

0.5，0.84，2.18，3.25，4.5

到此為止，排序結(jié)束。

?

public static double[] bucketSort(double[] array){//1.得到數(shù)列的最大值和最小值，并算出差值ddouble max = array[0];double min = array[0];for(int i=1; i<array.length; i++) {if(array[i] > max) {max = array[i];}if(array[i] < min) {min = array[i];}}double d = max - min;//2.初始化桶int bucketNum = array.length;ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);for(int i = 0; i < bucketNum; i++){bucketList.add(new LinkedList<Double>());}//3.遍歷原始數(shù)組，將每個(gè)元素放入桶中for(int i = 0; i < array.length; i++){int num = (int)((array[i] - min) ?* (bucketNum-1) / d);bucketList.get(num).add(array[i]);}//4.對(duì)每個(gè)通內(nèi)部進(jìn)行排序for(int i = 0; i < bucketList.size(); i++){//JDK底層采用了歸并排序或歸并的優(yōu)化版本Collections.sort(bucketList.get(i));}//5.輸出全部元素double[] sortedArray = new double[array.length];int index = 0;for(LinkedList<Double> list : bucketList){for(double element : list){sortedArray[index] = element;index++;}}return sortedArray;}public static void main(String[] args) {double[] array = new double[] {4.12,6.421,0.0023,3.0,2.123,8.122,4.12, 10.09};double[] sortedArray = bucketSort(array);System.out.println(Arrays.toString(sortedArray));}

代碼中，所有的桶保存在ArrayList集合當(dāng)中，每一個(gè)桶被定義成一個(gè)鏈表（LinkedList<Double>），這樣便于在尾部插入元素。

定位元素屬于第幾個(gè)桶，是按照比例來(lái)定位：

(array[i] - min)? * (bucketNum-1) / d

同時(shí)，代碼使用了JDK的集合工具類(lèi)Collections.sort來(lái)為桶內(nèi)部的元素進(jìn)行排序。Collections.sort底層采用的是歸并排序或Timsort，小伙伴們可以簡(jiǎn)單地把它們當(dāng)做是一種時(shí)間復(fù)雜度 O（nlogn）的排序。

?

假設(shè)原始數(shù)列有n個(gè)元素，分成m個(gè)桶（我們采用的分桶方式 m=n），平均每個(gè)桶的元素個(gè)數(shù)為n/m。

下面我們來(lái)逐步分析算法復(fù)雜度：

第一步求數(shù)列最大最小值，運(yùn)算量為n。

第二步創(chuàng)建空桶，運(yùn)算量為m。

第三步遍歷原始數(shù)列，運(yùn)算量為n。

第四步在每個(gè)桶內(nèi)部做排序，由于使用了O（nlogn）的排序算法，所以運(yùn)算量為 n/m?* log(n/m?) * m。

第五步輸出排序數(shù)列，運(yùn)算量為n。

?

加起來(lái)，總的運(yùn)算量為 3n+m+?n/m?* log(n/m?) * m =?3n+m+n(logn-logm) 。

去掉系數(shù)，時(shí)間復(fù)雜度為：

O(n+m+n(logn-logm)）?

至于空間復(fù)雜度就很明顯了：

空桶占用的空間 + 數(shù)列在桶中占用的空間 = O（m+n）。

?

?

?

?

?

?

?

總結(jié)

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

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