心血来潮，搞搞排序算法，这篇是PHP版的快速排序。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
<?php /** * 排序名称:快排. * * 说明: * 快速排序通常明显比同为Ο(n log n)的其他算法更快，因此常被采用， * 而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子. * * 步骤： * 1 从数列中挑出一个元素作为基准数。 * 2 分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。 * 3 再对左右区间递归执行第二步，直至各区间只有一个数。 * * @return void * * @author liujingyu **/ function quickSort(&$arr, $low, $high) { if ($low < $high) { $privotLoc = partition($arr, $low, $high); quickSort($arr, $low, $privotLoc-1); quickSort($arr, $privotLoc+1, $high); } return $arr; } function partition(&$arr, $low, $high) { $privotKey = $arr[$low]; while ($low < $high) { while ($low < $high and $arr[$high] >= $privotKey) { --$high; } list($arr[$low], $arr[$high]) = [$arr[$high], $arr[$low]]; while ($low < $high and $arr[$low] <= $privotKey) { ++$low; } list($arr[$low], $arr[$high]) = [$arr[$high], $arr[$low]]; } return $low; } |