溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章給大家分享的是有關如何在php項目中實現一個計數排序算法，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
計數排序只適合使用在鍵的變化不大于元素總數的情況下。它通常用作另一種排序算法（基數排序）的子程序，這樣可以有效地處理更大的鍵。
總之，計數排序是一種穩定的線性時間排序算法。計數排序使用一個額外的數組C ，其中第i個元素是待排序數組 A中值等于 i的元素的個數。然后根據數組C 來將A中的元素排到正確的位置。
通常計數排序算法的實現步驟思路是：
1.找出待排序的數組中最大和最小的元素；
2.統計數組中每個值為i的元素出現的次數，存入數組C的第i項；
3.對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
4.反向填充目標數組：將每個元素i放在新數組的第C[i]項，每放一個元素就將C[i]減去1。
PHP計數排序算法的實現代碼示例如下：
<?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 "原始數組 :\n";
echo implode(', ',$test_array );
echo "\n排序后數組\n:";
echo implode(', ',counting_sort($test_array, -1, 5)). PHP_EOL;輸出：
原始數組 : 3, 0, 2, 5, -1, 4, 1
排序后數組 :-1, 0, 1, 2, 3, 4, 5
下面補充一個例子
1、計數排序只適用于整數在小范圍內排序
<?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計數排序
獲取序列中的最小值min和最大值max O(n)
統計min - max之間所有值在序列中的出現次數 O(n)
順序輸出min - max的所有值,次數為0不輸出,其余次數為多少就輸出多少 O(k) k為數據范圍
例如序列為: 2, 4, 6, 9, 4, 8
min = 2, max = 9, n為6,k為8
統計出現次數為
[2 => 1, 3 => 0, 4 => 2, 5 => 0, 6 => 1, 7 => 0, 8 => 1, 9 => 1]
輸出結果為
2, 4, 4, 6, 8, 9
很明顯,計數排序的復雜度為O(n) + O(k),也就是和數據量和數據范圍有關.
若n和k相近,則可認為是O(n)
同時,因為要統計出現次數,如果數據范圍過大而數據又很稀疏,造成的空間浪費比較大
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項目中實現一個計數排序算法，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
