php 实现快速排序算法：

第一种：

1. 选取第一个元素为基数，分别从右（high）往左（high--）查找，找到一个比基数小的数，进行位置交换, 直到 low == high，结束一次排序；然后从 左 往右查找，找到一个比基数大的数，进行位置交换，直到 low == high，结束一次排序；最后将基数 放到 low 位置上。

2. 此时的 low 值代表一次排序后 基数所在的数组下标位置。

3. 通过递归进行 左右子数组排序，直到 low == high

代码如下：

$arr = [49,38,65,97,76,13,27,49]; function partition(&$arr, $low, $high) { //$low = 0; //$high = count($arr) - 1; $base = $arr[$low]; while($high > $low) { while($low < $high && $arr[$high] >= $base) { $high--; } $arr[$low] = $arr[$high]; while($low < $high && $arr[$low] <= $base) { $low++; } $arr[$high] = $arr[$low]; } $arr[$low] = $base; return $low; } function quickSort(&$arr, $low, $high) { if ($high > $low) { $pt = partition($arr, $low, $high); quickSort($arr, $low, $pt-1); quickSort($arr, $pt+1, $high); } } quickSort($arr, 0, count($arr)-1); print_r($arr);

 

第二种：

下面的排序，是使用到了PHP自带的 array_merge() 数组合并函数，并且通过循环遍历，每次都需要申请内存。

function quickSort1($arr) { $len = count($arr); if ($len <= 1) { return $arr; } $v = $arr[0]; $low = $up = array(); for ($i = 1; $i < $len; ++$i) { if ($arr[$i] > $v) { $up[] = $arr[$i]; } else { $low[] = $arr[$i]; } } $low = quickSort($low); $up = quickSort($up); $b = array_merge($low, array($v), $up); //print_r($b)."\n"; return $b; } $a = [6,1,3,2,8,5,9]; var_dump(quickSort($a));

---

待更。。。。

快排算法的应用：

 

1. 求无序数组中中位数

改变第一种方法里的 quickSort方法：

function quickSortMid(&$arr, $low, $high) { $size = count($arr); $mid = ceil(($size-1) / 2); // 当size为偶数时，向上取整。因为当pt 大于 mid时,中位数一定在左边数组，当等于时，中位数也一定包含在数组中 if ($high > $low) { $pt = partition($arr, $low, $high); if ($pt > $mid) { quickSortMid($arr, $low, $pt-1); } if ($pt < $mid) { quickSortMid($arr, $pt+1, $high); } if ($pt == $mid) { $high = $low; } } // 不需要返回值 // echo $low; // return $mid; } function findMid($arr) { $size = count($arr); $mid = ceil(($size - 1) /2); quickSortMid($arr, 0, $size - 1); print_r($arr); // 当为偶数时 if ($size % 2 == 0) { return ($arr[$mid] + $arr[$mid -1])/2; } else { return $arr[$mid]; } } $arr = [1,1,4,3]; var_dump(findMid($arr));

2. 求无序数组的第 k 大数