PHP排序算法之基數(shù)排序(Radix Sort)實例詳解

//交換函數(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ù)只是完成某一位（個位或十位）上的桶排序
 */
function R_Sort(array $arr,$loop){
  //桶數(shù)組，在強(qiáng)類型語言中，這個數(shù)組應(yīng)該聲明為[10][count($arr)]
  //第一維是 0-9 十個數(shù)
  //第二維這樣定義是因為有可能待排序的數(shù)組中的所有數(shù)的某一位上的只是一樣的，這樣就全擠在一個桶里面了
  $tempArr = array();
  $count = count($arr);
  //初始化$tempArr數(shù)組
  for($i = 0;$i  10;$i ++){
    $tempArr[$i] = array();
  }
  //求桶的index的除數(shù)
  //如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 ++){
    //求出某位上的數(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ù)據(jù)
      }
    }
  }
}
//最終調(diào)用的主函數(shù)
function RadixSort(array $arr){
  $max = getMax($arr);
  $loop = getLoopTimes($max);
  //對每一位進(jìn)行桶分配（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)
}

function R_Sort(array $arr,$loop){
  $tempArr = array();
  $count = count($arr);
  for($i = 0;$i  10;$i ++){
    $tempArr[$i] = array();
  }
  //求桶的index的除數(shù)
  //如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 ++){
    //求出某位上的數(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]);
    }
  }
}