詳解Bucket Sort桶排序算法及C++代碼實現(xiàn)示例
更新時間：2016年07月06日 16:36:17 作者：skywangkw
桶排序是一種線性排序算法,這里我們來詳解Bucket Sort桶排序算法及C++代碼實現(xiàn)示例,需要的朋友可以參考下
桶排序（Bucket sort）或所謂的箱排序，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的數(shù)組內的數(shù)值是均勻分配的時候，桶排序使用線性時間（Θ(n)）。但桶排序并不是比較排序，他不受到O(n log n)下限的影響。
桶排序以下列程序進行：
1.設置一個定量的數(shù)組當作空桶子。
2.尋訪序列，并且把項目一個一個放到對應的桶子去。
3.對每個不是空的桶子進行排序。
4.從不是空的桶子里把項目再放回原來的序列中。
桶排序圖文示例
桶排序代碼：
/*
* 桶排序
*
* 參數(shù)說明：
* a -- 待排序數(shù)組
* n -- 數(shù)組a的長度
* max -- 數(shù)組a中最大值的范圍
*/
void bucket_sort(int a[], int n, int max)
{
int i, j;
int *buckets;
if (a==NULL || n<1 || max<1)
return ;
// 創(chuàng)建一個容量為max的數(shù)組buckets，并且將buckets中的所有數(shù)據(jù)都初始化為0。
if ((buckets=(int *)malloc(max*sizeof(int)))==NULL)
return ;
memset(buckets, 0, max*sizeof(int));
// 1. 計數(shù)
for(i = 0; i < n; i++)
buckets[a[i]]++;
// 2. 排序
for (i = 0, j = 0; i < max; i++)
while( (buckets[i]--) >0 )
a[j++] = i;
free(buckets);
}
說明：
bucketSort(a, n, max)是作用是對數(shù)組a進行桶排序，n是數(shù)組a的長度，max是數(shù)組中最大元素所屬的范圍[0,max)。
假設a={8,2,3,4,3,6,6,3,9}, max=10。此時，將數(shù)組a的所有數(shù)據(jù)都放到需要為0-9的桶中。如下圖：
在將數(shù)據(jù)放到桶中之后，再通過一定的算法，將桶中的數(shù)據(jù)提出出來并轉換成有序數(shù)組。就得到我們想要的結果了。
相關文章
在C++中進行進制轉換可以通過標準庫函數(shù)或自定義算法實現(xiàn),本文主要為大家整理了兩種常見場景的轉換方法及示例代碼,有需要的小伙伴可以根據(jù)需求進行選擇2025-04-04
這篇文章主要介紹C++ 中的單例模式寫法，主要包括普通,2B,文藝三種寫法，需要的朋友可以參考下2013-03-03
這篇文章主要介紹了C語言中計算二叉樹的寬度的兩種方式的相關資料,需要的朋友可以參考下2017-04-04
這篇文章主要為大家詳細介紹了Qt中線程的使用方法，文中的示例代碼講解詳細，對我們學習Qt有一定的幫助，感興趣的小伙伴可以跟隨小編一起了解一下2022-12-12
這篇文章主要為大家詳細介紹了C++實現(xiàn)線性表鏈式存儲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
C++中的容器適配器和仿函數(shù)是實現(xiàn)數(shù)據(jù)結構與算法的重要技術，容器適配器可以將一個容器轉換為另一個形式，仿函數(shù)則可以自定義數(shù)據(jù)類型的比較、排序、計算等行為，提高程序的靈活性和可重用性2023-04-04
這篇文章主要為大家詳細介紹了C++STL函數(shù)和排序算法的快排以及歸并排序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
本篇文章是對C++輸入輸出操作符重載進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)BMP圖像處理，彩色圖轉灰度圖，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
這篇文章主要介紹了C語言之sizeof與strlen的使用及區(qū)別，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07