算法导论8.2-计数排序-小Y

<?php
/**
* 计数排序
* 找出数组A中的最大值k，通过数组C记录每个0-k之间每个数<=它的数有多少个，直接记录到在数组B中对应的位置
*/
function counting($array){
//找出最大的数
$max = 0;
foreach($array as $value){
if($value > $max)
$max = $value;
}
//在数组c中记录从0-max之间每个数的数量
$c = array();
for($i = 0; $i <= $max; $i++){
$c[$i] =0;
}
//print_r($c);
foreach($array as $value){
$c[$value] +=1;
}
//print_r($c);
//整理数组c中的数据，另每个元素记录的数据为小于等于他的数的个数
foreach($c as $key => $value){
if($key > 0)
$c[$key] += $c[$key-1];
}
//print_r($c);
//输出排序数组B
$b = array();
for($i = count($array)-1; $i >= 0; $i--){
$b[$c[$array[$i]]-1] = $array[$i];
$c[$array[$i]]--;
}
return $b;
}

$array = [10,3,4,2,7,9,8,6,1,5];
$array = counting($array, 0, 9);
for ($i = 0; $i < count($array); $i++){
echo $array[$i];
}

#include <stdio.h>

int counting_sort(int *A, int *B, int length, int k);

int main()
{
int A[10] = {3,6,10,8,4,2,7,1,9,5};
int B[10];
int i;
counting_sort(A, B, 10, 10);
for(i = 0; i < 10; i++){
printf("index:%d B:%d\n", i, B[i]);
}
return 0;
}

int counting_sort(int *A, int *B, int length, int k)
{
int C[k];
int i,j;

//init C[];
for(i = 0; i <= k; i++){
C[i] = 0;
}
//A[j]中等于i的元素个数
for(j = 0; j < length; j++){
C[A[j]] += 1;
}
//A[j]中小于等于i的元素个数
for (i = 1; i <= k; i++){
C[i] += C[i-1];
}
//输出排序数组B
for (j = length-1; j >= 0; j--){
B[C[A[j]]-1] = A[j];
C[A[j]]--;
}
return 1;
}

转载请注明：小Y » 算法导论8.2-计数排序

算法导论8.2-计数排序

相关推荐

评论抢沙发

相关推荐

评论 抢沙发

评论抢沙发