快捷導(dǎo)航

php計數(shù)排序算法的實現(xiàn)代碼(附四個實例代碼)

更新時間：2020年03月31日 22:48:14 投稿：mdxy-dxy

計數(shù)排序（Counting sort）是一種根據(jù)小整數(shù)鍵對一組對象排序的算法；也就是說，它是一個整數(shù)排序算法。它通過計算具有不同鍵值的對象的數(shù)量，并對這些數(shù)量使用算術(shù)來確定輸出序列中每個鍵值的位置

計數(shù)排序只適合使用在鍵的變化不大于元素總數(shù)的情況下。它通常用作另一種排序算法（基數(shù)排序）的子程序，這樣可以有效地處理更大的鍵。

總之，計數(shù)排序是一種穩(wěn)定的線性時間排序算法。計數(shù)排序使用一個額外的數(shù)組C ，其中第i個元素是待排序數(shù)組 A中值等于 i的元素的個數(shù)。然后根據(jù)數(shù)組C 來將A中的元素排到正確的位置。

通常計數(shù)排序算法的實現(xiàn)步驟思路是：

1.找出待排序的數(shù)組中最大和最小的元素；

2.統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項；

3.對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）；

4.反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第C[i]項，每放一個元素就將C[i]減去1。

PHP計數(shù)排序算法的實現(xiàn)代碼示例如下：

<?php
function counting_sort($my_array, $min, $max)
{
  $count = array();
  for($i = $min; $i <= $max; $i++)
  {
    $count[$i] = 0;
  }
 
  foreach($my_array as $number)
  {
    $count[$number]++;
  }
  $z = 0;
  for($i = $min; $i <= $max; $i++) {
    while( $count[$i]-- > 0 ) {
      $my_array[$z++] = $i;
    }
  }
  return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "原始數(shù)組 :\n";
echo implode(', ',$test_array );
echo "\n排序后數(shù)組\n:";
echo implode(', ',counting_sort($test_array, -1, 5)). PHP_EOL;

輸出：

原始數(shù)組 : 3, 0, 2, 5, -1, 4, 1

排序后數(shù)組 :-1, 0, 1, 2, 3, 4, 5

下面補充一個例子

1、計數(shù)排序只適用于整數(shù)在小范圍內(nèi)排序

<?php
$arr = [95,94,91,98,99,90,99,93,91,92];
function countSort($arr){
$max = $arr[0];
$min = $arr[0];
for($i=0;$i<count($arr);$i++){
if($arr[$i]>$max){
$max = $arr[$i];
}
if($arr[$i] < $min){
$min = $arr[$i];
}
}
try{
$frequency = new SplFixedArray($max-$min+1);
for($i=0;$i<count($arr);$i++){
if(empty($frequency[$arr[$i]-$min]))
$frequency[$arr[$i]-$min] = 0;
$frequency[$arr[$i]-$min] += 1;
}

$sum = 0;
for ($i=0; $i < count($frequency); $i++) {
$sum += $frequency[$i];
$frequency[$i] = $sum;
}

$splfixed = new SplFixedArray(count($arr));

for($i=(count($arr)-1);$i>=0;$i--){
$splfixed[$frequency[$arr[$i]-$min]-1] = $arr[$i];
$frequency[$arr[$i]-$min] -= 1;
}
}catch(RuntimeException $re){
echo "RuntimeException: ".$re->getMessage()."\n";
}
print_r($splfixed->toArray());
}
countSort($arr);
?>

輸出

Array
(
    [0] => 90
    [1] => 91
    [2] => 91
    [3] => 92
    [4] => 93
    [5] => 94
    [6] => 95
    [7] => 98
    [8] => 99
    [9] => 99
)

2、php計數(shù)排序

獲取序列中的最小值min和最大值max O(n)
統(tǒng)計min - max之間所有值在序列中的出現(xiàn)次數(shù) O(n)
順序輸出min - max的所有值,次數(shù)為0不輸出,其余次數(shù)為多少就輸出多少 O(k) k為數(shù)據(jù)范圍

例如序列為: 2, 4, 6, 9, 4, 8

min = 2, max = 9, n為6,k為8

統(tǒng)計出現(xiàn)次數(shù)為

[2 => 1, 3 => 0, 4 => 2, 5 => 0, 6 => 1, 7 => 0, 8 => 1, 9 => 1]

輸出結(jié)果為

2, 4, 4, 6, 8, 9

很明顯,計數(shù)排序的復(fù)雜度為O(n) + O(k),也就是和數(shù)據(jù)量和數(shù)據(jù)范圍有關(guān).
若n和k相近,則可認(rèn)為是O(n)
同時,因為要統(tǒng)計出現(xiàn)次數(shù),如果數(shù)據(jù)范圍過大而數(shù)據(jù)又很稀疏,造成的空間浪費比較大

class CountSort
{
  private $originalData = [];
  private $rangeMap = [];
  private $resultData = [];

  public function __construct($original = [])
  {
    $this->originalData = $original;
  }

  public function sort()
  {
    list($min, $max) = $this->calculateDataRange();
    $this->statisticNumberOfOccurrence($min, $max);
    $this->resultData = $this->generateResult();
    return $this->resultData;
  }

  protected function calculateDataRange()
  {
    $max = null;
    $min = null;

    foreach ($this->originalData as $value) {
      if (!is_null($max)) {
        if ($value > $max) {
          $max = $value;
        }
      } else {
        $max = $value;
      }

      if (!is_null($min)) {
        if ($value < $min) {
          $min = $value;
        }
      } else {
        $min = $value;
      }
    }

    return [$min, $max];
  }

  protected function statisticNumberOfOccurrence($min, $max)
  {
    for ($i = $min; $i <= $max; $i++) {
      $this->rangeMap[$i] = 0;
    }

    foreach ($this->originalData as $value) {
      $this->rangeMap[$value]++;
    }
  }

  protected function generateResult()
  {
    $result = [];

    foreach ($this->rangeMap as $key => $value) {
      if ($value != 0) {
        for ($i = 0; $i < $value; $i++) {
          array_push($result, $key);
        }
      }
    }
    return $result;
  }
}

$testData = [2, 3, 4, 3, 10, 30, 20, 15, 10, 12, 33];

$countSort = new CountSort($testData);
echo '<pre>';
var_dump($countSort->sort());

輸出

<pre>array(11) {
[0]=>
int(2)
[1]=>
int(3)
[2]=>
int(3)
[3]=>
int(4)
[4]=>
int(10)
[5]=>
int(10)
[6]=>
int(12)
[7]=>
int(15)
[8]=>
int(20)
[9]=>
int(30)
[10]=>
int(33)
}