java數完成演算法之桶排序的方法詳解

這篇文章主要介紹了java資料結構與演算法之桶排序實現方法,結合具體實例形式詳細分析了桶排序的概念、原理、實現方法與相關操作技巧,需要的朋友可以參考下

本文實例講述了java資料結構與演算法之桶排序實作方法。分享給大家供大家參考，具體如下：

基本思想：

假定輸入是由一個隨機過程產生的[0, M )區間上均勻分佈的實數。將區間[0, M)劃分為n個大小相等的子區間（桶），將n個輸入元素分配到這些桶中，對桶中元素進行排序，然後依次連接桶輸入0 ≤A[1.. n] 陣列B[0..n-1]是一指標數組，指向桶（鍊錶）。將n個記錄分佈到各桶中去。如果有多於一個記錄分到同一個桶中，需要進行桶內排序。最後依序把各個桶子裡的記錄列出來記得到有序序列。

[桶－關鍵字]對應函數

#bindex=f(key)   其中，bindex 為桶數組B的下標(即第bindex個桶), k為待排序列的關鍵字。桶排序之所以能夠高效，其關鍵在於這個映射函數，它必須做到：如果關鍵字k1很顯然，映射函數的確定與資料本身的特徵有很大的關係，我們下面舉個例子：

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

對上圖只要順序輸出每個B[i]中的資料就可以得到有序序列了。

演算法核心程式碼如下：

/// <summary>
/// 桶排序
///
///如果有重复的数字,则需要 List<int>数组,这里举的例子没有重复的数字
/// </summary>
/// <param name="unsorted">待排数组</param>
/// <param name="maxNumber">待排数组中的最大数,如果可以提供的话</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();
}

桶排序代價分析

桶排序利用函數的映射關係，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當於快排中劃分，已經把大量資料分割成了基本有序的資料塊(桶)。然後只需要對桶中的少量資料做先進的比較排序。

對N個關鍵字進行桶排序的時間複雜度分為兩個部分：

(1) 循環計算每個關鍵字的桶映射函數，這個時間複雜度是O(N)。
(2) 利用先進的比較排序演算法對每個桶內的所有資料進行排序，其時間複雜度為  ∑ O(Ni*logNi) 。其中Ni 為第i個桶的資料量。

很顯然，第(2)部分是桶排序性能好壞的決定因素。盡量減少桶內資料的數量是提高效率的唯一方法(因為基於比較排序的最好平均時間複雜度只能達到O(N*logN)了)。因此，我們需要盡量做到下面兩點：

(1) 映射函數f(k)能夠將N個資料平均的分配到M個桶中，這樣每個桶子就有[ N/M]個數據量。
(2) 盡量的增大桶的數量。極限情況下每個桶子只能得到一個數據，這樣就完全避開了桶內數據的「比較」排序操作。當然，做到這一點很不容易，在資料量龐大的情況下，f(k)函數會讓桶集合的數量龐大，空間浪費嚴重。這就是一個時間代價和空間代價的權衡問題了。

對於N個待排數據，M個桶，平均每個桶[N/M]個數據的桶排序平均時間複雜度為：

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

當N=M時，即極限情況下每個桶子只有一個資料時。桶排序的最佳效率能夠達到O(N)。

總結： 桶排序的平均時間複雜度為線性的O(N+C)，其中C=N*(logN-logM)。如果相對於同樣的N，桶數M越大，其效率越高，最好的時間複雜度達到O(N)。 當然桶排序的空間複雜度 為O(N+M)，如果輸入資料非常龐大，而桶的數量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩定的。

即以下三點：

1. 桶排序是穩定的
2. 桶排序是常見排序裡最快的一種,比快排還要快…大多數情況下
3. 桶排序非常快,但是同時也非常耗空間,基本上是最耗空間的一種排序演算法

#

補充：在尋找演算法中，基於比較的查找演算法最好的時間複雜度也是O(logN)。例如折半查找、平衡二元樹、紅黑樹等。但是Hash表卻有O(C)線性等級的查找效率(不衝突情況下查找效率達到O(1))。那麼：Hash表的思想和桶排序是不是有一曲同工之妙呢?

實際上，桶排序對資料的條件有特殊要求，如果數組很大的話，那麼分配幾億個桶顯然是不可能的。所以桶排序有其局限性，適合元素值集合不大的情況。

【相關推薦】

1. 特別推薦#：「php程式設計師工具箱」V0.1版本下載

2. Java免費影片教學

2. 全面解析Java註解

#

以上是java數完成演算法之桶排序的方法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！