資訊專欄INFORMATION COLUMN
摘要：一基數(shù)排序桶排序介紹來源百科基數(shù)排序屬于分配式排序，又稱桶子法或，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些桶中，藉以達到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時間復雜度為，其中為所采取的基數(shù)，而為堆數(shù)，在某些時候，基
一、基數(shù)排序(桶排序)介紹
來源360百科：
基數(shù)排序(radix sort)屬于"分配式排序"(distribution sort)，又稱"桶子法"(bucket sort)或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些"桶"中，藉以達到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。
從上面的簡單介紹，是并不了解基數(shù)排序是怎么弄的～基數(shù)排序不同與其他的7種排序，其他7種排序本質上都是按照交換或者比較來進行排序，但是基數(shù)排序并不是，它是按照分配，回收(分配到不同的位置上，然后回收)..不斷分配..回收來進行排序，直到有序..
聽上去好像很高大上，很難的樣子，其實不然。基數(shù)排序挺簡單的，下面我就來看一下基數(shù)排序的流程....
我們有9個桶，將數(shù)組的數(shù)字按照數(shù)值分配桶中：
ps:圖片來源于網(wǎng)絡，侵刪
上面我們發(fā)現(xiàn)：如果將桶按順序進行回收，那么我們的排序就完成了～
可是，一般我們的數(shù)組元素都不僅僅是個位數(shù)的數(shù)字的呀，那么高位數(shù)的數(shù)字又怎么弄呢？？比如：23,44,511,6234這些高位數(shù)..
其實也是一樣的：
第一趟桶排序將數(shù)字的個位數(shù)分配到桶子里面去，然后回收起來，此時數(shù)組元素的所有個位數(shù)都已經(jīng)排好順序了
第二趟桶排序將數(shù)字的十位數(shù)分別分配到桶子里面去，然后回收起來，此時數(shù)組元素的所有個位數(shù)和十位數(shù)都已經(jīng)排好順序了(如果沒有十位數(shù)、則補0)
第三趟桶排序將數(shù)字的百位數(shù)分別分配到桶子里面去，然后回收起來，此時數(shù)組元素的所有個位數(shù)和十位數(shù)和百位數(shù)都已經(jīng)排好順序了(如果沒有百位數(shù)、則補0)
..................................
直至全部數(shù)(個、十、百、千位...)排好順序，那么這個數(shù)組就是有序的了。
ps:圖片來源于網(wǎng)絡，侵刪
機智的同學可能就會發(fā)現(xiàn)了，關于這個桶我們可以用二維數(shù)組來進行存放。
10個桶子就是10列，如果分配時有的數(shù)字相同的話，那么就弄成多行~
二、基數(shù)排序體驗首先我們有以下這個數(shù)組：
int[] arrays = {6, 4322, 432, 344, 55 };
現(xiàn)在我們有10個桶子，每個桶子下能裝載arrays.length個數(shù)字..
int[][] buckets = new int[arrays.length][10];
效果如下：
2.1第一趟分配與回收將數(shù)組的每個個位數(shù)進行分配到不同的桶子上：
分配完之后，我們按照順序來進行回收：得到的結果應該是這樣子的：{4322,432,344,55,6}
2.2第二趟分配與回收將數(shù)組的每個十位數(shù)進行分配到不同的桶子上(像6這樣的數(shù)，往前邊補0)：
于是我們可以得到這樣的排序：
分配完之后，我們按照順序來進行回收：得到的結果應該是這樣子的：{6,4322,432,344,55}
2.3第三趟分配與回收將數(shù)組的每個百位數(shù)進行分配到不同的桶子上(像6、55這樣的數(shù)，往前邊補0)：
于是我們可以得到這樣的排序：
分配完之后，我們按照順序來進行回收：得到的結果應該是這樣子的：{6,55,4322,344,432}
2.3第四趟分配與回收將數(shù)組的每個百位數(shù)進行分配到不同的桶子上(像6、55，344，432這樣的數(shù)，往前邊補0)：
于是我們可以得到這樣的排序：
分配完之后，我們按照順序來進行回收：得到的結果應該是這樣子的：{6,55,344,432,4322}
此時我們的數(shù)組就已經(jīng)可以排好序了~~~過程就是這樣子，其實不難就只有兩個步驟：
將數(shù)組的每一位放進桶子里
回收
循環(huán)......
三、基數(shù)排序代碼編寫我們的基數(shù)排序是按照個、十、百、千位...來進行存放的。前面的演示是已經(jīng)知道數(shù)組元素的數(shù)據(jù)的情況下來進行存放，但是一般我們是不去理會數(shù)組內元素的值的。那如果位數(shù)很多(萬位)或者都是個位數(shù)，這個條件我們怎么去處理呢？
我們可以這樣做：先求出數(shù)組最大的值，然后不斷/10，只要它能大于0，那么它的位數(shù)還有~：
3.1求出數(shù)組最大的值這個我在前面寫遞歸的時候就有這個代碼了，我就直接搬去遞歸的代碼過來了，順便復習一哈吧：
當然了，更好的是直接用for循環(huán)來找出來就行了(易讀性好一些)
/**
* 遞歸，找出數(shù)組最大的值
* @param arrays 數(shù)組
* @param L 左邊界，第一個數(shù)
* @param R 右邊界，數(shù)組的長度
* @return
*/
public static int findMax(int[] arrays, int L, int R) {
//如果該數(shù)組只有一個數(shù)，那么最大的就是該數(shù)組第一個值了
if (L == R) {
return arrays[L];
} else {
int a = arrays[L];
int b = findMax(arrays, L + 1, R);//找出整體的最大值
if (a > b) {
return a;
} else {
return b;
}
}
3.2代碼實現(xiàn)
public static void radixSort(int[] arrays) {
int max = findMax(arrays, 0, arrays.length - 1);
//需要遍歷的次數(shù)由數(shù)組最大值的位數(shù)來決定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arrays.length][10];
//獲取每一位數(shù)字(個、十、百、千位...分配到桶子里)
for (int j = 0; j < arrays.length; j++) {
int num = (arrays[j] / i) % 10;
//將其放入桶子里
buckets[j][num] = arrays[j];
}
//回收桶子里的元素
int k = 0;
//有10個桶子
for (int j = 0; j < 10; j++) {
//對每個桶子里的元素進行回收
for (int l = 0; l < arrays.length ; l++) {
//如果桶子里面有元素就回收(數(shù)據(jù)初始化會為0)
if (buckets[l][j] != 0) {
arrays[k++] = buckets[l][j];
}
}
}
}
}
搞了一堆數(shù)測試了一哈：
四、總結基數(shù)排序(桶排序)要理解起來并不困難，不過值得注意的是：基數(shù)排序對有負數(shù)和0的數(shù)列難以進行排序
因此，往往有0和負數(shù)的數(shù)組一般我們都不用基數(shù)來進行排序
基數(shù)排序的要點就兩個：
分配：按照元素的大小來放入不同的桶子里
回收：將桶子里的元素按桶子順序重新放到數(shù)組中
重復.....兩個步驟
參考資料：
http://www.cnblogs.com/skywang12345/p/3603669.html
http://www.cnblogs.com/developerY/p/3172379.html
https://www.cnblogs.com/zengzhihua/p/4456753.html
https://www.cnblogs.com/jin-nuo/p/5293554.html
https://www.cnblogs.com/protected/p/6603536.html
https://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html
如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要獲取更多的Java資源的同學，可以關注微信公眾號:Java3y
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76379.html
摘要：涉及的算法有計數(shù)排序基數(shù)排序桶排序，它們被歸類為非比較排序。計數(shù)排序沒有對元素進行比較，只是利用了箱與元素的一一對應關系，根據(jù)箱已經(jīng)排好序的先決條件，解決排序。基數(shù)排序，是按照從高位到低位的順序進行分組排序。內部排序也是用基數(shù)排序。 一般算法能做到O(logn)，已經(jīng)非常不錯，如果我們排序的對象是純數(shù)字，還可以做到驚人的O(n)。涉及的算法有計數(shù)排序、基數(shù)排序、桶排序，它們被歸類為非比...
摘要：不斷執(zhí)行這個操作代碼實現(xiàn)快速排序用遞歸比較好寫如果不太熟悉遞歸的同學可到遞歸就這么簡單。 前言 大概花了一周的時間把八大基礎排序過了一遍，這篇博文主要是用來回顧一下八大基礎排序的要點和一些總結～ 回顧： 冒泡排序就這么簡單 選擇排序就這么簡單 插入排序就這么簡單 快速排序就這么簡單 歸并排序就這么簡單 堆排序就這么簡單 希爾排序就這么簡單 基數(shù)排序就這么簡單 總的來說：快速排序是用...
摘要：適用于數(shù)據(jù)比較少或基本有序的情況。插入排序時間復雜度為，空間復雜度為，屬于穩(wěn)定排序。算法適用于少量數(shù)據(jù)的排序。就像下圖這樣，可以理解桶的意思下圖是整個排序過程示意圖基數(shù)排序時間復雜度為，空間復雜度為，屬于穩(wěn)定排序。 寫在前面 個人感覺：javascript對類似排序查找這樣的功能已經(jīng)有了很好的封裝，以致于當我們想對數(shù)組排序的時候只需要調用arr.sort()方法，而查找數(shù)組元素也只需要...
摘要：操作符如何使用索引有一些查詢完全無法使用索引，也有一些查詢能夠比其他查詢更高效地使用索引。有時能夠使用索引，但是通常它并不知道要如何使用索引。索引對象和數(shù)組允許深入文檔內部，對嵌套字段和數(shù)組建立索引。 上一篇文章：MongoDB指南---10、索引、復合索引 簡介下一篇文章：MongoDB指南---12、使用explain()和hint()、何時不應該使用索引 1、使用復合索引 在多...
摘要：操作符如何使用索引有一些查詢完全無法使用索引，也有一些查詢能夠比其他查詢更高效地使用索引。有時能夠使用索引，但是通常它并不知道要如何使用索引。索引對象和數(shù)組允許深入文檔內部，對嵌套字段和數(shù)組建立索引。 上一篇文章：MongoDB指南---10、索引、復合索引 簡介下一篇文章：MongoDB指南---12、使用explain()和hint()、何時不應該使用索引 1、使用復合索引 在多...
閱讀 576·2023-04-26 01:42
閱讀 3222·2021-11-22 11:56
閱讀 2392·2021-10-08 10:04
閱讀 836·2021-09-24 10:37
閱讀 3125·2019-08-30 15:52
閱讀 1732·2019-08-29 13:44
閱讀 472·2019-08-28 17:51
閱讀 2141·2019-08-26 18:26
