<?php
$arr = [];
$len = 100000;
for ($i = 0; $i < $len; $i++) {
$arr[] = mt_rand(0, $len);
}
function qsort(&$arr, $s, $e)
{
$l = $e - $s; // count within the problem set
$pivot = $s + mt_rand(0, $l);
$smallerCount = 0;
for ($i = $s; $i <= $e; $i++) {
if ($arr[$i] < $arr[$pivot]) {
$smallerCount++;
}
}
$fPivot = $smallerCount + $s;
// fix pivot position
if ($fPivot !== $pivot) {
swap($arr, $pivot, $fPivot);
}
unset($pivot);
$leastBigger = $fPivot + 1;
for ($i = $s; $i < $fPivot; $i++) {
if ($arr[$i] < $arr[$fPivot]) {
continue;
}
for ($j = $leastBigger; $j <= $e; $j++) {
if ($arr[$j] < $arr[$fPivot]) {
swap($arr, $j, $i);
$leastBigger = $j + 1;
break;
}
}
}
if ($s < $fPivot - 1) {
qsort($arr, $s, $fPivot - 1);
}
if ($e > $fPivot + 1) {
qsort($arr, $fPivot + 1, $e);
}
}
function swap(&$arr, $a, $b)
{
$tmp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $tmp;
/**
$arr[$a] ^= $arr[$b];
$arr[$b] ^= $arr[$a];
$arr[$a] ^= $arr[$b];
**/
}
function verify($arr)
{
for ($i = 0, $l = count($arr) - 1; $i < $l; $i++) {
if ($arr[$i] > $arr[$i + 1]) {
return false;
}
}
return true;
}
$start = microtime(true);
qsort($arr, 0, $len - 1);
assert(true === verify($arr));
echo PHP_VERSION, "\n";
echo "sort $len elements\n";
echo "Time consumed: ", microtime(true) - $start, "\n";
echo "Mem consumed: ", memory_get_peak_usage(true) / 1024 / 1024, "MB\n";
智一面热门岗位面试题：
