PHP 使用归并排序或计数排序

一、归并排序

<?php

$count = (int)fgets(STDIN);
$flag = (int)fgets(STDIN);
$grades = [];
for($i = 0; $i < $count; $i++) {
    fscanf(STDIN, '%s %d', $grades[ $i ][0], $grades[ $i ][1]);
}

if($flag == 1) {
    usersort($grades, function($a, $b) { return $a[1]-$b[1]; });
} else {
    usersort($grades, function($a, $b) { return $b[1]-$a[1]; });
}

foreach($grades as $grade) {
    echo $grade[0] . ' ' . $grade[1] . "\n";
}


function usersort(&$arr, $compare) {
    merge_sort($arr, 0, count($arr)-1, $compare);
}

function merge_sort(&$arr, $start, $end, $compare) {
    if($start >= $end) {
        return;
    }
    
    $mid = $start+(($end-$start)>>1); // 注意 >> 符号优先级比 + 号还低，这个坑了我一个小时我去。
    merge_sort($arr, $start, $mid, $compare);
    merge_sort($arr, $mid+1, $end, $compare);
    
    $temp = [];
    $i = $start;
    $j = $mid+1;
    while($i <= $mid && $j <= $end) {
        $temp[] = $compare($arr[$i], $arr[$j]) > 0 ? $arr[$j++] : $arr[$i++];
    }
    while($i <= $mid) {
        $temp[] = $arr[$i++];
    }
    while($j <= $end) {
        $temp[] = $arr[$j++];
    }
    
    for($i = $start; $i <= $end; $i++) {
        $arr[$i] = $temp[ $i-$start ];
    }
}

二、计数排序

<?php

$count = (int)fgets(STDIN);
$flag = (int)fgets(STDIN);
$grades = [];
for($i = 0; $i < $count; $i++) {
    fscanf(STDIN, '%s %d', $grades[ $i ][0], $grades[ $i ][1]);
}

usersort($grades, function($a) { return $a[1]; }, 100, $flag ? SORT_ASC : SORT_DESC);

foreach($grades as $grade) {
    echo $grade[0] . ' ' . $grade[1] . "\n";
}


function usersort(&$arr, $key, $max, $flag) {
    $bucket = [];
    foreach($arr as $el) {
        $index = $key($el);
        if( ! isset($bucket[ $index ])) {
            $bucket[ $index ] = [ $el ];
        } else {
            $bucket[ $index ][] = $el;
        }
    }
    
    if($flag == SORT_ASC) {
        for($i = 0, $curr = 0; $i <= $max; $i++) {
            while($bucket[ $i ]) {
                $arr[$curr++] = array_shift($bucket[ $i ]);
            }
        }
    } else {
        for($i = $max, $curr = 0; $i >= 0; $i--) {
            while($bucket[ $i ]) {
                $arr[$curr++] = array_shift($bucket[ $i ]);
            }
        }
    }
}