原創公衆号：bigsai
前言
在排序算法中，大家可能對桶排序、計數排序、基數排序不太了解，不太清楚其算法的思想和流程，也可能看過會過但是很快就忘記了，但是不要緊，幸運的是你看到了本篇文章。本文将通俗易懂的給你講解基數排序。
基數排序，是一種原理簡單，但實作複雜的排序。很多人在學習基數排序的時候可能會遇到以下兩種情況而淺嘗辄止：
- 一看原理，這麼簡單，懂了懂了(順便溜了)
- 再一看代碼，這啥啥啥啊？這些的肯定有問題(不看溜了)
要想深入了解基數排序，必須搞懂基數排序各種形式(數字類型、等長字元類型、不等長字元)各自實作方法，了解其中的聯系和差別，并且也要掌握空間優化的方法(非二維數組而僅用一維數組)。下面跟着我詳細學習基數排序吧！
基數排序原理
首先百度百科看看基數排序的定義：
基數排序（radix sort）屬于“配置設定式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，将要排序的元素配置設定至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，基數排序法的效率高于其它的穩定性排序法。
基數排序也稱為卡片排序，簡而言之，基數排序的原理就是多次利用計數排序(計數排序是一種特殊的桶排序)，但是和前面的普通桶排序和計數排序有所差別的是，基數排序并不是将一個整體配置設定到一個桶中，而是将自身拆分成一個個組成的元素，每個元素分别順序配置設定放入桶中、順序收集，當從前往後或者從後往前每個位置都進行過這樣順序的配置設定、收集後，就獲得了一個有序的數列。
在具體實作上如果從左往右那就是最高位優先(Most Significant Digit first)法，簡稱MSD法；如果從右往左那就是最低位優先(Least Significant Digit first)法，簡稱LSD法。但是不管從最高位開始還是從最低位開始要保證和相同位進行比較，你需要注意的是如果是int等數字類型需要保證從右往左(從低位到高位)保證對齊，如果是字元類型的話需要從左往右(從高位到低位)保證對齊。
你可能會問為啥不直接将這個數或者這個數按照區間範圍放到對應的桶中，一方面基數排序可能很多時候處理的是字元型的資料，不友善放入某個桶中，另一方面如果數字很大，不友善直接放入桶中。并且基數排序并不需要交換，也不需要比較，就是多次配置設定、收集得到結果。
是以遇到這種情況我們基數排序思想很簡單，就拿 934，241，3366，4399這幾個數字進行基數排序的一趟過程來看，第一次會根據各位進行配置設定、收集：
配置設定和收集都是有序的，第二次會根據十位進行配置設定、收集，此次是在第一次個位配置設定、收集基礎上進行的，是以所有數字單看個位十位是有序的。
而第三次就是對百位進行配置設定收集，此次完成之後百位及其以下是有序的。
而最後一次的時候進行處理的時候，千位有的數字需要補零，這次完畢後後千位及以後都有序，即整個序列排序完成。
想必看到這裡基數排序的思想你也已經懂了吧，但是雖然懂你不一定能夠寫出代碼來，繼續看看下面的分析和實作。
數字類型基數排序
有很多時候也有很多時候對基數排序的講解也是基于數字類型的，而數字類型這裡就用int來實作，對于數字類型的基數排序你需要注意的有以下幾點：
- 無論是最高位優先法還是最低位優先法進行周遊需要保證數字各位、十位、百位等對齊，這裡我使用最低位優先法從個位開始向上。
- 數字類型的基數排序需要十個桶(0-9)，你可以使用二維數組，第一次元長度為10表示十個數字，第二個次元為數組長度，用來存儲數字(因為最壞情況可能目前位數字一樣)。但這樣無疑太浪費記憶體空間了，你可以使用List或者Queue替代，這裡就用List了。
- 具體實作要先找到最大值确定最高多少位，用來進行周遊時候确認。
- 收集的時候借助一個自增參數周遊收集。
- 每次收集完畢十個桶(bucket)需要清空待下次收集。
實作的代碼為：
static void radixSort(int[] arr)//int 類型 從右往左
{
List<Integer>bucket[]=new ArrayList[10];
for(int i=0;i<10;i++)
{
bucket[i]=new ArrayList<Integer>();
}
//找到最大值
int max=0;//假設都是正數
for(int i=0;i<arr.length;i++)
{
if(arr[i]>max)
max=arr[i];
}
int divideNum=1;//1 10 100 100……用來求對應位的數字
while (max>0) {//max 和num 控制
for(int num:arr)
{
bucket[(num/divideNum)%10].add(num);//配置設定 将對應位置的數字放到對應bucket中
}
divideNum*=10;
max/=10;
int idx=0;
//收集 重新撿起資料
for(List<Integer>list:bucket)
{
for(int num:list)
{
arr[idx++]=num;
}
list.clear();//收集完需要清空留下次繼續使用
}
}
} 等長字元串基數排序
除了數字之外，等長字元串也是常常遇到的方式，其主要方法和數字類型差不多，這裡也看不出政策上的不同。低位優先法或者高位優先法都可使用(這裡依舊低位從右向左)。
在實作細節方面，和前面的數字類型差別不是很大，但是因為字元串是等長的周遊更加友善容易。但需要額外注意的是：
- 字元類型的桶bucket不是10個而是ASCII字元的個數(根據實際需要檢視ASCII表)。其實就是利用char和int之間關系可以直接按照每個字元進行順序存儲。
具體實作代碼為：
static void radixSort(String arr[],int len)//等長字元排序情況 長度為len
{
List<String>buckets[]=new ArrayList[128];
for(int i=0;i<128;i++)
{
buckets[i]=new ArrayList<String>();
}
for(int i=len-1;i>=0;i--)//每一位上進行操作
{
for(String str:arr)
{
buckets[str.charAt(i)].add(str);//配置設定
}
int idx=0;
for(List<String>list:buckets)
{
for(String str:list)
{
arr[idx++]=str;//收集
}
list.clear();//收集完該bucket清空
}
}
} 非等長字元串基數排序
等長的字元串進行基數排序時候很好周遊，那麼非等長的時候該如何考慮呢？這種非等長不能像處理數字那樣粗暴的計算當成0即可。字元串的大小是從前往後進行排列的(和長度沒關系)。例如看下面字元串，“d”這個字元串即使很短但是在排序依然放在最後面。你知道該怎麼處理嗎？
"abigsai"
"bigsai"
"bigsaisix"
"d" 如果高位優先，前面一旦比較過各個字元的桶(bucket)就要固定下來，也就是在進行右面下一個字元配置設定、收集的時候要标記空間，即下次進行配置設定收集的前面是‘a’字元的一組，‘b’字元一組，并且不能越界，實作起來很麻煩這裡就不詳細講解了有興趣的可以自行研究一下。
而本篇實作的是低位優先。低位優先采用什麼思路呢？很簡單，跟我看圖解。
第一步，先将字元按照長度進行配置設定到一個桶(bucket)中，聲明一個
List<String>wordLen[maxlen+1]
;在周遊字元時候，以字元長度為下表index，将字元串順序加入進去。其中maxlen為最長字元串長度，之是以要maxlen+1是因為需要使用maxlen下标(0-maxlen)。
第二步，配置設定完成周遊收集到原數組中，這樣原數組在長度上相對有序。
這樣就可以進行基數排序啦，當然，在開始的時候并不是全部都進行配置設定收集，而是根據長度慢慢遞減，長度可以到達6位配置設定、收集，長度到達5的配置設定、收集……長度為1的進行配置設定、收集。這樣進行一遭就很完美的進行完基數排序，因為我們借助根據長度收集的桶可以很容易知道目前長度開始的index在哪裡。
具體實作的代碼為：
static void radixSort(String arr[])//字元不等長的情況進行排序
{
//找到最長的那個
int maxlen=0;
for(String team:arr)
{
if(team.length()>maxlen)
maxlen=team.length();
}
//一個對長度分 一個對具體字元分，先用長度來找到
List<String>wordLen[]=new ArrayList[maxlen+1];//用長度先統計各個長度的單詞
List<String>bucket[]=new ArrayList[128];//根據字元來劃分
for(int i=0;i<wordLen.length;i++)
wordLen[i]=new ArrayList<String>();
for(int i=0;i<bucket.length;i++)
bucket[i]=new ArrayList<String>();
//先根據長度來一下
for(String team:arr)
{
wordLen[team.length()].add(team);
}
int index=0;//先進行一次(按照長度分)的桶排序使得數組長度初步有序
for(List<String>list:wordLen)
{
for(String team:list)
{
arr[index++]=team;
}
}
//然後 先進行長的 從後往前進行
int startIndex=arr.length;
for(int len=maxlen;len>0;len--)//每次長度相同的要進行基數一次
{
int preIndex=startIndex;
startIndex-=wordLen[len].size();
for(int i=startIndex;i<arr.length;i++)
{
bucket[arr[i].charAt(len-1)].add(arr[i]);//利用字元桶重新裝
}
//重新收集
index=startIndex;
for(List<String>list:bucket)
{
for(String str:list)
{
arr[index++]=str;
}
list.clear();
}
}
} 空間優化(等長字元)基數排序
上面無論是等長還是不等長，使用的空間其實都是跟二維相關的，我們能不能使用一維的空間去解決這個問題呢？當然能啊。
在使用空間的整個思路是差不多的，但是這裡為了讓你能夠了解我們在講解的時候講解等長字元串的情況。
先回憶剛剛講的等長字元串，就是從個位進行周遊，在周遊的時候将資料放到對應的桶裡面，然後在進行收集的時候放回原數組。
你能否發現什麼規律？
- 一個字元串收集的時候放的位置其實它隻需要知道它前面有多少個就可以确定！
- 并且目前位置字元如果相同那麼就是根據arr中相對順序來進行目前輪。
是以我們可以嘗試來動态維護這個int bucket[]。第一次進行隻記錄次數，第二次進行疊加表示比目前位置+1編号小的元素的個數。
但是這樣處理不太好知道比目前位置小的有多少，是以我們在配置設定的時候向下挪一位，這樣bucket[i]就可以表示比目前位置小的元素的個數。
我們在進行收集的時候需要再次周遊arr，但我們需要一個臨時數組String value[]儲存結果(因為arr沒周遊完後面不能使用)，而進行周遊的規則就是：周遊arr時候對應字元串str，該位字元對應
bucket[str.charAt(i)]
桶中數字就是要放到arr中的編号(多少個比它小的就放到第多少位)，放置之後要對bucket目前位自增(因為下一個這個位置字元串要把這個str考慮進去)。這樣到最後即可完成排序。
第一趟周遊arr前兩個字元串部分過程如下：
第一趟中間兩個字元串處理情況：
第一趟最後兩個字元串處理情況：
就這樣即可完成一趟操作，一趟完成記得将value的值指派到arr中，當然有方法使用指針引用可以避免交換資料帶來的時間影響，但這裡為了使大家更加簡單了解就直接複制過去。這樣完成若幹次，整個基數排序即可完成。
static void radixSortByArr(String arr[],int len)//固定長度的使用數組進行優化
{
int charLen=129;//多用一個
String value[]=new String[arr.length];
for(int index=len-1;index>=0;index--)//不同的位置
{
int bucket[]=new int[charLen];//儲存character的桶
for(int i=0;i<arr.length;i++)//配置設定
{
bucket[(int)(arr[i].charAt(index)+1)]++;
}
for(int i=1;i<bucket.length;i++)//疊加 目前i位置表示比自己小的個數
{
bucket[i]+=bucket[i-1];
}
for(int i=0;i<arr.length;i++)
{
value[bucket[arr[i].charAt(index)]++]=arr[i];//中間的++因為目前位置填充了一個，下次再來同元素就要後移
}
System.arraycopy(value,0,arr,0,arr.length);//copy數組
}
} 至于不定長的，思路也差不多，這裡就留給你優秀的你自己去思考啦。
結語
至于基數排序的算法分析，以定長的情況分析，假設有n數字(字元串)，每個有k位，那麼根據基數就要每一位都周遊就是K次，每次都是O(n)級别。是以差不多是O(n*k)級别，當然k遠遠小于n，可能有成千上萬個數，但是每個數或者字元正常可沒成千上萬那麼長。
本次基數排序就全講完啦，那麼多張圖我想你也應該懂了。
最後我請你們兩連事幫忙一下:
- 點贊、關注一下支援， 您的肯定是我在平台創作的源源動力。
- 微信搜尋「bigsai」，關注我的公衆号，不僅免費送你電子書，我還會第一時間在公衆号分享知識技術。加我還可拉你進力扣打卡群一起打卡LeetCode。
記得關注、咱們下次再見！