php 实现计数排序

算法还是很重要嘀~
直接贴代码:

<?php
/*
 * count_sort.php 计数排序
 * cli 模式运行 php count_sort.php 3 4 5 6 3 2 4 56 4 3 2 8 1
 */
$a = $argv;
unset($a[0]);
$n = count($a);
// 找出数组中最大的数
$k = 0;
for ($i = 1; $i <= $n; $i++) {
	if ($k < $a[$i])
		$k = $a[$i];
}
// 初始化数组 $c
$c[0]= 0;
for ($i = 1; $i <= $k; $i++)
	$c[$i] = 0;

for ($i = 1; $i <= $n; $i++) {
	$c[$a[$i]]++;
}// 此时 $c[$i] 包含等于 $i 的元素个数

for ($i = 1; $i <= $k; $i++) {
	$c[$i] = $c[$i-1] + $c[$i];
}// 此时 $c[$i] 包含小于或等于 $i 的元素个数

for ($i = $n; $i >= 1; $i--) {
	$b[$c[$a[$i]]] = $a[$i];
	$c[$a[$i]]--;
}
// 输出已排好序的数组
for ($i = 1; $i <= $n; $i++)
	echo $b[$i] . ' ';
echo "\n";

 

今天又重新梳理了一遍,不能根据这个代码看出计数排序是稳定排序:

<?php
/** 
 * 计数排序
 */
$nums = [23,12,23,34,23,456,23,12,23,45,23,12,1234];

$n = count($nums);

// 找出数组中最大的数
$max = $nums[0];
for ($i = 1; $i < $n; $i++) {
        if ($max < $nums[$i]) {
                $max = $nums[$i];
        }
}

// 初始化用来计数的数组
for ($i = 0; $i <= $max; $i++) {
        $cnt[$i] = 0;
}

// 下面的 for loop 处理完毕后,$cnt[$i] 表示待排序数组中,值等于 $i 的元素个数
for ($i = 0; $i < $n; $i++) {
        $cnt[$nums[$i]]++;
}

// 下面的 for loop 处理完毕后,$cnt[$i] 表示待排序数组中,值小于等于 $i 的元素个数
for ($i = 1; $i <= $max; $i++) {
        $cnt[$i] = $cnt[$i-1] + $cnt[$i];
}

// 这一步比较难理解
for ($i = $n-1; $i >= 0; $i--) {
      $result[$cnt[$nums[$i]]] = $nums[$i];
      $cnt[$nums[$i]]--; // 前一个数找到位置后,那么和它值相同的数位置往前一步
}

for ($i = 1; $i < $n; $i++) {
        echo $result[$i], ' ';
}
echo PHP_EOL;

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注