java數(shù)據(jù)結構與算法之桶排序實現(xiàn)方法詳解-創(chuàng)新互聯(lián)

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

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

基本思想：

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

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

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

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

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

算法核心代碼如下：

/// <summary>
/// 桶排序
///
///如果有重復的數(shù)字,則需要 List<int>數(shù)組,這里舉的例子沒有重復的數(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();
}

文章名稱：java數(shù)據(jù)結構與算法之桶排序實現(xiàn)方法詳解-創(chuàng)新互聯(lián)
標題網(wǎng)址：http://bm7419.com/article24/ggoce.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設計公司、網(wǎng)站策劃、電子商務、品牌網(wǎng)站設計、標簽優(yōu)化、網(wǎng)站制作

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

猜你還喜歡下面的內容