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

創新互聯是一家企業級云計算解決方案提供商,超15年IDC數據中心運營經驗。主營GPU顯卡服務器，站群服務器，成都服務器托管，海外高防服務器，服務器機柜，動態撥號VPS，海外云手機，海外云服務器，海外服務器租用托管等。

基本思想：

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

[桶——關鍵字]映射函數

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

假如待排序列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();
}

文章名稱：java數據結構與算法之桶排序實現方法詳解-創新互聯
標題網址：http://vcdvsql.cn/article24/ggoce.html

成都網站建設公司_創新互聯，為您提供網站設計公司、網站策劃、電子商務、品牌網站設計、標簽優化、網站制作

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯