您好,登錄后才能下訂單哦!
本篇文章給大家分享的是有關(guān)如何在php項(xiàng)目中實(shí)現(xiàn)一個計(jì)數(shù)排序算法,小編覺得挺實(shí)用的,因此分享給大家學(xué)習(xí),希望大家閱讀完這篇文章后可以有所收獲,話不多說,跟著小編一起來看看吧。
計(jì)數(shù)排序只適合使用在鍵的變化不大于元素總數(shù)的情況下。它通常用作另一種排序算法(基數(shù)排序)的子程序,這樣可以有效地處理更大的鍵。
總之,計(jì)數(shù)排序是一種穩(wěn)定的線性時間排序算法。計(jì)數(shù)排序使用一個額外的數(shù)組C ,其中第i個元素是待排序數(shù)組 A中值等于 i的元素的個數(shù)。然后根據(jù)數(shù)組C 來將A中的元素排到正確的位置。
通常計(jì)數(shù)排序算法的實(shí)現(xiàn)步驟思路是:
1.找出待排序的數(shù)組中最大和最小的元素;
2.統(tǒng)計(jì)數(shù)組中每個值為i的元素出現(xiàn)的次數(shù),存入數(shù)組C的第i項(xiàng);
3.對所有的計(jì)數(shù)累加(從C中的第一個元素開始,每一項(xiàng)和前一項(xiàng)相加);
4.反向填充目標(biāo)數(shù)組:將每個元素i放在新數(shù)組的第C[i]項(xiàng),每放一個元素就將C[i]減去1。
PHP計(jì)數(shù)排序算法的實(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
下面補(bǔ)充一個例子
1、計(jì)數(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計(jì)數(shù)排序
獲取序列中的最小值min和最大值max O(n)
統(tǒng)計(jì)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)計(jì)出現(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
很明顯,計(jì)數(shù)排序的復(fù)雜度為O(n) + O(k),也就是和數(shù)據(jù)量和數(shù)據(jù)范圍有關(guān).
若n和k相近,則可認(rèn)為是O(n)
同時,因?yàn)橐y(tǒng)計(jì)出現(xiàn)次數(shù),如果數(shù)據(jù)范圍過大而數(shù)據(jù)又很稀疏,造成的空間浪費(fèi)比較大
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)
}
以上就是如何在php項(xiàng)目中實(shí)現(xiàn)一個計(jì)數(shù)排序算法,小編相信有部分知識點(diǎn)可能是我們?nèi)粘9ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學(xué)到更多知識。更多詳情敬請關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。