桶排序就是這么容易
前言
1.桶排序(Bucket sort)
2.原理
2.1.關(guān)鍵
2.2.算法過程
3.代碼
4.擴(kuò)展閱讀
前言
聲明：參考來源互聯(lián)網(wǎng)，有任何爭議可以留言。站在前人的肩上，我們才能看的更遠(yuǎn)。
本教程純手打，致力于最實(shí)用教程，不需要什么獎勵，只希望多多轉(zhuǎn)發(fā)支持。 歡迎來我公眾號，希望可以結(jié)識你，也可以催更，微信搜索：JavaPub
有任何問題都可以來談?wù)?！
如果看上一篇**計(jì)數(shù)排序，你有沒有這樣疑問，當(dāng)每個數(shù)據(jù)之間跨度過大(如從 0-2億 數(shù)字中排序 20 個數(shù))，就需要大量空間消耗。桶排序就是對計(jì)數(shù)排序**的改進(jìn)。
1.桶排序(Bucket sort)
百度百科:
桶排序 (Bucket sort)或所謂的箱排序，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是 鴿巢排序 的一種歸納結(jié)果。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
繼續(xù) -->
桶排序是**計(jì)數(shù)排序的升級版。它利用了函數(shù)的映射關(guān)系**，高效與否的關(guān)鍵就在于這個映射函數(shù)的確定。為了使桶排序更加高效，我們需要做到這兩點(diǎn)：
在額外空間充足的情況下，盡量增大桶的數(shù)量
使用的映射函數(shù)能夠?qū)⑤斎氲?N 個數(shù)據(jù)均勻的分配到 K 個桶中
同時，對于桶中元素的排序，選擇何種比較排序算法對于性能的影響至關(guān)重要。
桶排序是將待排序集合中處于同一個值域的元素存入同一個桶中，也就是根據(jù)元素值特性將集合拆分為多個區(qū)域，則拆分后形成的多個桶，從值域上看是處于有序狀態(tài)的。對每個桶中元素進(jìn)行排序，則所有桶中元素構(gòu)成的集合是已排序的。
快速排序是將集合拆分為兩個值域，這里稱為兩個桶，再分別對兩個桶進(jìn)行排序，最終完成排序。桶排序則是將集合拆分為多個桶，對每個桶進(jìn)行排序，則完成排序過程。兩者不同之處在于，快排是在集合本身上進(jìn)行排序，屬于原地排序方式，且對每個桶的排序方式也是快排。桶排序則是提供了額外的操作空間，在額外空間上對桶進(jìn)行排序，避免了構(gòu)成桶過程的元素比較和交換操作，同時可以自主選擇恰當(dāng)?shù)呐判蛩惴▽ν斑M(jìn)行排序。
2.原理
2.1.關(guān)鍵
元素值域的劃分，也就是元素到桶的映射規(guī)則。映射規(guī)則需要根據(jù)待排序集合的元素分布特性進(jìn)行選擇，若規(guī)則設(shè)計(jì)的過于模糊、寬泛，則可能導(dǎo)致待排序集合中所有元素全部映射到一個桶上，則桶排序向比較性質(zhì)排序算法演變。若映射規(guī)則設(shè)計(jì)的過于具體、嚴(yán)苛，則可能導(dǎo)致待排序集合中每一個元素值映射到一個桶上，則桶排序向計(jì)數(shù)排序方式演化。
排序算法的選擇，從待排序集合中元素映射到各個桶上的過程，并不存在元素的比較和交換操作，在對各個桶中元素進(jìn)行排序時，可以自主選擇合適的排序算法，桶排序算法的復(fù)雜度和穩(wěn)定性，都根據(jù)選擇的排序算法不同而不同。
2.2.算法過程
根據(jù)待排序集合中最大元素和最小元素的差值范圍和映射規(guī)則，確定申請的桶個數(shù)；
遍歷待排序集合，將每一個元素移動到對應(yīng)的桶中；
對每一個桶中元素進(jìn)行排序，并移動到已排序集合中。
步驟 3 中提到的已排序集合，和步驟 1、2 中的待排序集合是同一個集合。與計(jì)數(shù)排序不同，桶排序的步驟 2 完成之后，所有元素都處于桶中，并且對桶中元素排序后，移動元素過程中不再依賴原始集合，所以可以將桶中元素移動回原始集合即可。
示意圖
元素分配到不同桶中：
然后，元素在每個桶中排序：
3.代碼
基于 Java 的代碼，代碼邏輯很好理解，使用到插入排序，如果不理解，點(diǎn)擊傳送。
package?utils;
import?java.util.Arrays;
/**
?*?@author?wangshiyu?rodert
?*?@date?2020/6/21?15:13
?*?@description
?*/
public?class?BucketSort?{
????public?static?void?main(String[]?args)?throws?Exception?{
????????int[]?array?=?{2,?1,?5,?3,?4};
????????BucketSort?bucketSort?=?new?BucketSort();
????????int[]?sort?=?bucketSort.sort(array);
????????System.out.println(Arrays.toString(sort));
????}
????private?static?final?InsertSort?insertSort?=?new?InsertSort();
????public?int[]?sort(int[]?sourceArray)?throws?Exception?{
????????//?對?arr?進(jìn)行拷貝，不改變參數(shù)內(nèi)容
????????int[]?arr?=?Arrays.copyOf(sourceArray,?sourceArray.length);
????????return?bucketSort(arr,?5);
????}
????private?int[]?bucketSort(int[]?arr,?int?bucketSize)?throws?Exception?{
????????if?(arr.length?==?0)?{
????????????return?arr;
????????}
????????int?minValue?=?arr[0];
????????int?maxValue?=?arr[0];
????????for?(int?value?:?arr)?{
????????????if?(value?<?minValue)?{
????????????????minValue?=?value;
????????????}?else?if?(value?>?maxValue)?{
????????????????maxValue?=?value;
????????????}
????????}
????????int?bucketCount?=?(int)?Math.floor((maxValue?-?minValue)?/?bucketSize)?+?1;//向下取整?+?1
????????int[][]?buckets?=?new?int[bucketCount][0];
????????//?利用映射函數(shù)將數(shù)據(jù)分配到各個桶中
????????for?(int?i?=?0;?i?<?arr.length;?i++)?{
????????????int?index?=?(int)?Math.floor((arr[i]?-?minValue)?/?bucketSize);
????????????buckets[index]?=?arrAppend(buckets[index],?arr[i]);
????????}
????????int?arrIndex?=?0;
????????for?(int[]?bucket?:?buckets)?{
????????????if?(bucket.length?<=?0)?{
????????????????continue;
????????????}
????????????//?對每個桶進(jìn)行排序，這里使用了插入排序
????????????bucket?=?insertSort.sort(bucket);
????????????for?(int?value?:?bucket)?{
????????????????arr[arrIndex++]?=?value;
????????????}
????????}
????????return?arr;
????}
????/**
?????*?自動擴(kuò)容，并保存數(shù)據(jù)
?????*
?????*?@param?arr
?????*?@param?value
?????*/
????private?int[]?arrAppend(int[]?arr,?int?value)?{
????????arr?=?Arrays.copyOf(arr,?arr.length?+?1);
????????arr[arr.length?-?1]?=?value;
????????return?arr;
????}
}
class?InsertSort?{
????//插入排序
????public?int[]?sort(int[]?sourceArray)?throws?Exception?{
????????//?對?arr?進(jìn)行拷貝，不改變參數(shù)內(nèi)容
????????int[]?arr?=?Arrays.copyOf(sourceArray,?sourceArray.length);
????????//?從下標(biāo)為1的元素開始選擇合適的位置插入，因?yàn)橄聵?biāo)為0的只有一個元素，默認(rèn)是有序的
????????for?(int?i?=?1;?i?<?arr.length;?i++)?{
????????????//?記錄要插入的數(shù)據(jù)
????????????int?tmp?=?arr[i];
????????????//?從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)
????????????int?j?=?i;
????????????while?(j?>?0?&&?tmp?<?arr[j?-?1])?{
????????????????arr[j]?=?arr[j?-?1];
????????????????j--;
????????????}
????????????//?存在比其小的數(shù)，插入
????????????if?(j?!=?i)?{
????????????????arr[j]?=?tmp;
????????????}
????????}
????????return?arr;
????}
}
返回結(jié)果：
[1,?2,?3,?4,?5]
Arrays.copyOf()方法理解：用于復(fù)制指定的數(shù)組內(nèi)容以達(dá)到擴(kuò)容的目的，該方法對不同的基本數(shù)據(jù)類型都有對應(yīng)的重載方法。
4.擴(kuò)展閱讀
真題：347. Top K Frequent Elements (Medium)，給定一個非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。
Given a non-empty array of integers, return the k most frequent elements.
題解：
//基于桶排序求解「前?K?個高頻元素」
class?Solution?{
????public?List<Integer>?topKFrequent(int[]?nums,?int?k)?{
????????List<Integer>?res?=?new?ArrayList();
????????//?使用字典，統(tǒng)計(jì)每個元素出現(xiàn)的次數(shù)，元素為鍵，元素出現(xiàn)的次數(shù)為值
????????HashMap<Integer,Integer>?map?=?new?HashMap();
????????for(int?num?:?nums){
????????????if?(map.containsKey(num))?{
???????????????map.put(num,?map.get(num)?+?1);
?????????????}?else?{
????????????????map.put(num,?1);
?????????????}
????????}
????????
????????//桶排序
????????//將頻率作為數(shù)組下標(biāo)，對于出現(xiàn)頻率不同的數(shù)字集合，存入對應(yīng)的數(shù)組下標(biāo)
????????List<Integer>[]?list?=?new?List[nums.length+1];
????????for(int?key?:?map.keySet()){
????????????//?獲取出現(xiàn)的次數(shù)作為下標(biāo)
????????????int?i?=?map.get(key);
????????????if(list[i]?==?null){
???????????????list[i]?=?new?ArrayList();
????????????}?
????????????list[i].add(key);
????????}
????????
????????//?倒序遍歷數(shù)組獲取出現(xiàn)順序從大到小的排列
????????for(int?i?=?list.length?-?1;i?>=?0?&&?res.size()?<?k;i--){
????????????if(list[i]?==?null)?continue;
????????????res.addAll(list[i]);
????????}
????????return?res;
????}
}
```桶排序就是這么容易
