PHP排序算法中基數(shù)排序Radix Sort的示例分析

這篇文章主要為大家展示了“PHP排序算法中基數(shù)排序Radix Sort的示例分析”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“PHP排序算法中基數(shù)排序Radix Sort的示例分析”這篇文章吧。

本文實(shí)例講述了PHP排序算法之基數(shù)排序(Radix Sort)。分享給大家供大家參考，具體如下：

基數(shù)排序在《大話數(shù)據(jù)結(jié)構(gòu)》中并未講到，但是為了湊齊八大排序算法，我自己通過網(wǎng)絡(luò)學(xué)習(xí)了這個(gè)排序算法，并給大家分享出來。

基本思想：

基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。

其實(shí)這個(gè)思想我也沒法總結(jié)出來，下面通過例子來說明吧：

基本解法：

PS：在這里我們介紹的基數(shù)排序我們采用 LSD（最低位優(yōu)先），當(dāng)然還有 MSD（最高位優(yōu)先），大家自己去百度一下他們之間的異同吧。

假如現(xiàn)在我們有以下這么一些數(shù)：

2 343 342 1 128 43 4249 814 687 654 3

我們使用基數(shù)排序?qū)⑺麄儚男〉酱笈判颉?/p>

第一步、首先根據(jù)個(gè)位數(shù)的數(shù)值，在走訪數(shù)值（從前到后走訪，后面步驟相同）時(shí)將它們分配至編號(hào)0到9的桶子中：

0 :
1 : 1
2 : 2 342
3 : 343 43 3
4 : 814 654
5 :
6 :
7 : 687
8 : 128
9 : 4249

第二步、接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：

1 2 342 343 43 3 814 654 687 128 4249

第三步、根據(jù)十位數(shù)的數(shù)值，在走訪數(shù)值（從前到后走訪，后面步驟相同）時(shí)將它們分配至編號(hào)0到9的桶子中：

0 : 1 2 3
1 : 814
2 : 128
3 :
4 : 342 343 43 4249
5 : 654
6 :
7 :
8 : 687
9 :

第四步、接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：

1 2 3 814 128 342 343 43 4249 654 687

第五步、根據(jù)百位數(shù)的數(shù)值，在走訪數(shù)值（從前到后走訪，后面步驟相同）時(shí)將它們分配至編號(hào)0到9的桶子中：

0 : 1 2 3 43
1 : 128
2 : 4249
3 : 342 343
4 :
5 :
6 : 654 687
7 :
8 : 814
9 :

第六步、接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：

1 2 3 43 128 4249 342 343 654 687 814

。。。。。。后面的步驟大家應(yīng)該都會(huì)走了吧。其實(shí)到了第六步的時(shí)候就剩 4249 沒有排好序了。

從上面的步驟來看，很多的步驟都是相同的，因此肯定是個(gè)循環(huán)了，我們只需要控制個(gè)位、十位、百位、、、、就好了。

還是看代碼吧。

算法實(shí)現(xiàn)：

//交換函數(shù)
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//獲取數(shù)組中的最大數(shù)
//就像上面的例子一樣，我們最終是否停止算法不過就是看數(shù)組中的最大值：4249，它的位數(shù)就是循環(huán)的次數(shù)
function getMax(array $arr){
  $max = 0;
  $length = count($arr);
  for($i = 0;$i < $length;$i ++){
    if($max < $arr[$i]){
      $max = $arr[$i];
    }
  }
  return $max;
}
//獲取最大數(shù)的位數(shù),最大值的位數(shù)就是我們分配桶的次數(shù)
function getLoopTimes($maxNum){
  $count = 1;
  $temp = floor($maxNum / 10);
  while($temp != 0){
    $count ++;
    $temp = floor($temp / 10);
  }
  return $count;
}
/**
 * @param array $arr 待排序數(shù)組
 * @param $loop 第幾次循環(huán)標(biāo)識(shí)
 * 該函數(shù)只是完成某一位（個(gè)位或十位）上的桶排序
 */
function R_Sort(array &$arr,$loop){
  //桶數(shù)組，在強(qiáng)類型語(yǔ)言中，這個(gè)數(shù)組應(yīng)該聲明為[10][count($arr)]
  //第一維是 0-9 十個(gè)數(shù)
  //第二維這樣定義是因?yàn)橛锌赡艽判虻臄?shù)組中的所有數(shù)的某一位上的只是一樣的，這樣就全擠在一個(gè)桶里面了
  $tempArr = array();
  $count = count($arr);
  //初始化$tempArr數(shù)組
  for($i = 0;$i < 10;$i ++){
    $tempArr[$i] = array();
  }
  //求桶的index的除數(shù)
  //如798個(gè)位桶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 ++){
    //求出某位上的數(shù)字
    $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;
      }
    }
  }
  //還原回原數(shù)組中
  $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;  //避免下次循環(huán)的時(shí)候污染數(shù)據(jù)
      }
    }
  }
}
//最終調(diào)用的主函數(shù)
function RadixSort(array &$arr){
  $max = getMax($arr);
  $loop = getLoopTimes($max);
  //對(duì)每一位進(jìn)行桶分配（1 表示個(gè)位，$loop 表示最高位）
  for($i = 1;$i <= $loop;$i ++){
    R_Sort($arr,$i);
  }
}

調(diào)用算法：

$arr = array(2, 343, 342, 1, 128, 43, 4249, 814, 687, 654, 3);
RadixSort($arr);
var_dump($arr);

運(yùn)行結(jié)果：

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)
}

其實(shí)這些代碼我是在挺早之前寫的，今天在寫博客的時(shí)候發(fā)現(xiàn)，其實(shí)桶就是一個(gè)隊(duì)列，所以上面的 R_Sort()函數(shù)復(fù)雜了，我們使用 array_push() 和 array_shift() 來重寫該方法（當(dāng)然，要模擬隊(duì)列的話，用 SPL 提供的 splqueue 是最為恰當(dāng)?shù)?，在這里為了簡(jiǎn)便我就不用了）：

function R_Sort(array &$arr,$loop){
  $tempArr = array();
  $count = count($arr);
  for($i = 0;$i < 10;$i ++){
    $tempArr[$i] = array();
  }
  //求桶的index的除數(shù)
  //如798個(gè)位桶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 ++){
    //求出某位上的數(shù)字
    $row_index = ($arr[$i] / $tempNum) % 10;
    //入桶
    array_push($tempArr[$row_index],$arr[$i]);
  }
  //還原回原數(shù)組中
  $k = 0;
  for($i = 0;$i < 10;$i ++){
    //出桶
    while(count($tempArr[$i]) > 0){
      $arr[$k ++] = array_shift($tempArr[$i]);
    }
  }
}

基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)。

以上是“PHP排序算法中基數(shù)排序Radix Sort的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！