本文實例講述了PHP排序算法之基數排序(Radix Sort)。分享給大家供大家參考，具體如下：
基數排序在《大話數據結構》中并未講到，但是為了湊齊八大排序算法，我自己通過網絡學習了這個排序算法，并給大家分享出來。
基本思想：
基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的穩定性排序法。
其實這個思想我也沒法總結出來，下面通過例子來說明吧：
基本解法：
PS：在這里我們介紹的基數排序我們采用 LSD（最低位優先），當然還有 MSD（最高位優先），大家自己去百度一下他們之間的異同吧。
假如現在我們有以下這么一些數：
2 343 342 1 128 43 4249 814 687 654 3
我們使用基數排序將他們從小到大排序。
第一步、首先根據個位數的數值，在走訪數值（從前到后走訪，后面步驟相同）時將它們分配至編號0到9的桶子中：
0 :
1 : 1
2 : 2 342
3 : 343 43 3
4 : 814 654
5 :
6 :
7 : 687
8 : 128
9 : 4249
第二步、接下來將這些桶子中的數值重新串接起來，成為以下的數列：
1 2 342 343 43 3 814 654 687 128 4249
第三步、根據十位數的數值，在走訪數值（從前到后走訪，后面步驟相同）時將它們分配至編號0到9的桶子中：
0 : 1 2 3
1 : 814
2 : 128
3 :
4 : 342 343 43 4249
5 : 654
6 :
7 :
8 : 687
9 :
第四步、接下來將這些桶子中的數值重新串接起來，成為以下的數列：
1 2 3 814 128 342 343 43 4249 654 687
第五步、根據百位數的數值，在走訪數值（從前到后走訪，后面步驟相同）時將它們分配至編號0到9的桶子中：
0 : 1 2 3 43
1 : 128
2 : 4249
3 : 342 343
4 :
5 :
6 : 654 687
7 :
8 : 814
9 :
第六步、接下來將這些桶子中的數值重新串接起來，成為以下的數列：
1 2 3 43 128 4249 342 343 654 687 814
。。。。。。后面的步驟大家應該都會走了吧。其實到了第六步的時候就剩 4249 沒有排好序了。
從上面的步驟來看，很多的步驟都是相同的，因此肯定是個循環了，我們只需要控制個位、十位、百位、、、、就好了。
還是看代碼吧。
算法實現：
//交換函數
function swap(array $arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
//獲取數組中的最大數
//就像上面的例子一樣，我們最終是否停止算法不過就是看數組中的最大值：4249，它的位數就是循環的次數
function getMax(array $arr){
$max = 0;
$length = count($arr);
for($i = 0;$i $length;$i ++){
if($max $arr[$i]){
$max = $arr[$i];
}
}
return $max;
}
//獲取最大數的位數,最大值的位數就是我們分配桶的次數
function getLoopTimes($maxNum){
$count = 1;
$temp = floor($maxNum / 10);
while($temp != 0){
$count ++;
$temp = floor($temp / 10);
}
return $count;
}
/**
* @param array $arr 待排序數組
* @param $loop 第幾次循環標識
* 該函數只是完成某一位（個位或十位）上的桶排序
*/
function R_Sort(array $arr,$loop){
//桶數組，在強類型語言中，這個數組應該聲明為[10][count($arr)]
//第一維是 0-9 十個數
//第二維這樣定義是因為有可能待排序的數組中的所有數的某一位上的只是一樣的，這樣就全擠在一個桶里面了
$tempArr = array();
$count = count($arr);
//初始化$tempArr數組
for($i = 0;$i 10;$i ++){
$tempArr[$i] = array();
}
//求桶的index的除數
//如798個位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//$tempNum為上式中的1、10、100
$tempNum = (int)pow(10, $loop - 1);
for($i = 0;$i $count;$i ++){
//求出某位上的數字
$row_index = ($arr[$i] / $tempNum) % 10;
for($j = 0;$j $count;$j ++){
if(@$tempArr[$row_index][$j] == NULL){
$tempArr[$row_index][$j] = $arr[$i]; //入桶
break;
}
}
}
//還原回原數組中
$k = 0;
for($i = 0;$i 10;$i ++){
for($j = 0;$j $count;$j ++){
if(@$tempArr[$i][$j] != NULL){
$arr[$k ++] = $tempArr[$i][$j]; //出桶
$tempArr[$i][$j] = NULL; //避免下次循環的時候污染數據
}
}
}
}
//最終調用的主函數
function RadixSort(array $arr){
$max = getMax($arr);
$loop = getLoopTimes($max);
//對每一位進行桶分配（1 表示個位，$loop 表示最高位）
for($i = 1;$i = $loop;$i ++){
R_Sort($arr,$i);
}
}
調用算法：
$arr = array(2, 343, 342, 1, 128, 43, 4249, 814, 687, 654, 3);
RadixSort($arr);
var_dump($arr);
運行結果：
array(11) {
[0]=>
int(1)
[1]=>
int(2)
[2]=>
int(3)
[3]=>
int(43)
[4]=>
int(128)
[5]=>
int(342)
[6]=>
int(343)
[7]=>
int(654)
[8]=>
int(687)
[9]=>
int(814)
[10]=>
int(4249)
}
其實這些代碼我是在挺早之前寫的，今天在寫博客的時候發現，其實桶就是一個隊列，所以上面的 R_Sort()函數復雜了，我們使用 array_push() 和 array_shift() 來重寫該方法（當然，要模擬隊列的話，用 SPL 提供的 splqueue 是最為恰當的，在這里為了簡便我就不用了）：
function R_Sort(array $arr,$loop){
$tempArr = array();
$count = count($arr);
for($i = 0;$i 10;$i ++){
$tempArr[$i] = array();
}
//求桶的index的除數
//如798個位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//$tempNum為上式中的1、10、100
$tempNum = (int)pow(10, $loop - 1);
for($i = 0;$i $count;$i ++){
//求出某位上的數字
$row_index = ($arr[$i] / $tempNum) % 10;
//入桶
array_push($tempArr[$row_index],$arr[$i]);
}
//還原回原數組中
$k = 0;
for($i = 0;$i 10;$i ++){
//出桶
while(count($tempArr[$i]) > 0){
$arr[$k ++] = array_shift($tempArr[$i]);
}
}
}
基數排序法是屬于穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數。
好了，到這里基數排序就已經給大家介紹完了。這個算法的總結主要是通過看網上的資料，所以就不再給出原作者了。
PS：這里再為大家推薦一款關于排序的演示工具供大家參考：
在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多關于PHP相關內容感興趣的讀者可查看本站專題：《php排序算法總結》、《PHP數據結構與算法教程》、《php程序設計算法總結》、《php字符串(string)用法總結》、《PHP數組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結》及《PHP數學運算技巧總結》
希望本文所述對大家PHP程序設計有所幫助。
您可能感興趣的文章:- PHP排序算法之歸并排序(Merging Sort)實例詳解
- PHP排序算法之快速排序(Quick Sort)及其優化算法詳解
- PHP排序算法之堆排序(Heap Sort)實例詳解
- PHP排序算法之希爾排序(Shell Sort)實例分析
- PHP排序算法之直接插入排序(Straight Insertion Sort)實例分析
- PHP排序算法之簡單選擇排序(Simple Selection Sort)實例分析
- php中sort函數排序知識點總結
