快捷導(dǎo)航

java數(shù)據(jù)結(jié)構(gòu)與算法之桶排序?qū)崿F(xiàn)方法詳解

更新時(shí)間：2017年05月03日 09:50:09 作者：android小豬

這篇文章主要介紹了java數(shù)據(jù)結(jié)構(gòu)與算法之桶排序?qū)崿F(xiàn)方法,結(jié)合具體實(shí)例形式詳細(xì)分析了桶排序的概念、原理、實(shí)現(xiàn)方法與相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了java數(shù)據(jù)結(jié)構(gòu)與算法之桶排序?qū)崿F(xiàn)方法。分享給大家供大家參考，具體如下：

基本思想：

假定輸入是由一個(gè)隨機(jī)過程產(chǎn)生的[0, M)區(qū)間上均勻分布的實(shí)數(shù)。將區(qū)間[0, M)劃分為n個(gè)大小相等的子區(qū)間（桶），將n個(gè)輸入元素分配到這些桶中，對桶中元素進(jìn)行排序，然后依次連接桶輸入0 ≤A[1..n] <M輔助數(shù)組B[0..n-1]是一指針數(shù)組，指向桶（鏈表）。將n個(gè)記錄分布到各個(gè)桶中去。如果有多于一個(gè)記錄分到同一個(gè)桶中，需要進(jìn)行桶內(nèi)排序。最后依次把各個(gè)桶中的記錄列出來記得到有序序列。

[桶——關(guān)鍵字]映射函數(shù)

bindex=f(key) 其中，bindex 為桶數(shù)組B的下標(biāo)(即第bindex個(gè)桶), k為待排序列的關(guān)鍵字。桶排序之所以能夠高效，其關(guān)鍵在于這個(gè)映射函數(shù)，它必須做到：如果關(guān)鍵字k1<k2，那么f(k1)<=f(k2)。也就是說B(i)中的最大數(shù)據(jù)都要小于B(i+1)中最小數(shù)據(jù)。很顯然，映射函數(shù)的確定與數(shù)據(jù)本身的特點(diǎn)有很大的關(guān)系，我們下面舉個(gè)例子：

假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。這些數(shù)據(jù)全部在1—100之間。因此我們定制10個(gè)桶，然后確定映射函數(shù)f(k)=k/10。則第一個(gè)關(guān)鍵字49將定位到第4個(gè)桶中(49/10=4)。依次將所有關(guān)鍵字全部堆入桶中，并在每個(gè)非空的桶中進(jìn)行快速排序后得到如下圖所示：

對上圖只要順序輸出每個(gè)B[i]中的數(shù)據(jù)就可以得到有序序列了。

算法核心代碼如下：

/// <summary>
/// 桶排序
///
///如果有重復(fù)的數(shù)字,則需要 List<int>數(shù)組,這里舉的例子沒有重復(fù)的數(shù)字
/// </summary>
/// <param name="unsorted">待排數(shù)組</param>
/// <param name="maxNumber">待排數(shù)組中的最大數(shù),如果可以提供的話</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();
}

桶排序代價(jià)分析

桶排序利用函數(shù)的映射關(guān)系，減少了幾乎所有的比較工作。實(shí)際上，桶排序的f(k)值的計(jì)算，其作用就相當(dāng)于快排中劃分，已經(jīng)把大量數(shù)據(jù)分割成了基本有序的數(shù)據(jù)塊(桶)。然后只需要對桶中的少量數(shù)據(jù)做先進(jìn)的比較排序即可。

對N個(gè)關(guān)鍵字進(jìn)行桶排序的時(shí)間復(fù)雜度分為兩個(gè)部分：

(1) 循環(huán)計(jì)算每個(gè)關(guān)鍵字的桶映射函數(shù)，這個(gè)時(shí)間復(fù)雜度是O(N)。
(2) 利用先進(jìn)的比較排序算法對每個(gè)桶內(nèi)的所有數(shù)據(jù)進(jìn)行排序，其時(shí)間復(fù)雜度為 ∑ O(Ni*logNi) 。其中Ni 為第i個(gè)桶的數(shù)據(jù)量。

很顯然，第(2)部分是桶排序性能好壞的決定因素。盡量減少桶內(nèi)數(shù)據(jù)的數(shù)量是提高效率的唯一辦法(因?yàn)榛诒容^排序的最好平均時(shí)間復(fù)雜度只能達(dá)到O(N*logN)了)。因此，我們需要盡量做到下面兩點(diǎn)：

(1) 映射函數(shù)f(k)能夠?qū)個(gè)數(shù)據(jù)平均的分配到M個(gè)桶中，這樣每個(gè)桶就有[N/M]個(gè)數(shù)據(jù)量。
(2) 盡量的增大桶的數(shù)量。極限情況下每個(gè)桶只能得到一個(gè)數(shù)據(jù)，這樣就完全避開了桶內(nèi)數(shù)據(jù)的“比較”排序操作。當(dāng)然，做到這一點(diǎn)很不容易，數(shù)據(jù)量巨大的情況下，f(k)函數(shù)會(huì)使得桶集合的數(shù)量巨大，空間浪費(fèi)嚴(yán)重。這就是一個(gè)時(shí)間代價(jià)和空間代價(jià)的權(quán)衡問題了。

對于N個(gè)待排數(shù)據(jù)，M個(gè)桶，平均每個(gè)桶[N/M]個(gè)數(shù)據(jù)的桶排序平均時(shí)間復(fù)雜度為：

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

當(dāng)N=M時(shí)，即極限情況下每個(gè)桶只有一個(gè)數(shù)據(jù)時(shí)。桶排序的最好效率能夠達(dá)到O(N)。

總結(jié)： 桶排序的平均時(shí)間復(fù)雜度為線性的O(N+C)，其中C=N*(logN-logM)。如果相對于同樣的N，桶數(shù)量M越大，其效率越高，最好的時(shí)間復(fù)雜度達(dá)到O(N)。當(dāng)然桶排序的空間復(fù)雜度為O(N+M)，如果輸入數(shù)據(jù)非常龐大，而桶的數(shù)量也非常多，則空間代價(jià)無疑是昂貴的。此外，桶排序是穩(wěn)定的。

即以下三點(diǎn)：

1. 桶排序是穩(wěn)定的
2. 桶排序是常見排序里最快的一種,比快排還要快…大多數(shù)情況下
3. 桶排序非常快,但是同時(shí)也非常耗空間,基本上是最耗空間的一種排序算法

補(bǔ)充：在查找算法中，基于比較的查找算法最好的時(shí)間復(fù)雜度也是O(logN)。比如折半查找、平衡二叉樹、紅黑樹等。但是Hash表卻有O(C)線性級(jí)別的查找效率(不沖突情況下查找效率達(dá)到O(1))。那么：Hash表的思想和桶排序是不是有一曲同工之妙呢?

實(shí)際上，桶排序?qū)?shù)據(jù)的條件有特殊要求，如果數(shù)組很大的話，那么分配幾億個(gè)桶顯然是不可能的。所以桶排序有其局限性，適合元素值集合并不大的情況。

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對大家java程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: