PHP实现快速排序

快速排序

思想：从数组中选一个数字作为基准数字，然后将数组进行遍历，比此数大的数字放一个数组里，比此数小的数字放另一个数组里。然后递归调用，最终合并数组。

特点：最坏的时间复杂度为O(n^2)，不稳定，例如下面的2个相同数字5，谁排前后不确定。

<?php declare(strict_types=1);

function quickSort(array $aNum): array
{
   $iLen = count($aNum);
   if ($iLen > 1) {
       $iNum = $aNum[0];
       $aLow = [];
       $aHigh = [];
       for ($i = 1; $i < $iLen; $i++) {
           $aNum[$i] >= $iNum ? array_push($aHigh, $aNum[$i]) : array_push($aLow, $aNum[$i]);
       }
       $aLow = quickSort($aLow);
       $aHigh = quickSort($aHigh);

       return array_merge($aLow, [$iNum], $aHigh);
   }

   return $aNum;
}

print_r(quickSort([2, 5, 3, 78, 5, 8]));