快速排序算法的时间复杂度和各次标准数据元素的值关系很大。如果每次选取的标准元素都能均分两个子数组的长度,这样的快速排序过程是一个完全二叉树结构。(即每个结点都把当前数组分成两个大小相等的数组结点,n个元素数组的根结点的分解次数就构成一棵完全二叉树)。这时分解次数等于完全二叉树的深度log2n;每次快速排序过程无论把数组怎样划分、全部的比较次数都接近于n-1次，所以最好情况下快速排序算法的时间复杂度为O(nlog2n):快速排序算法的最坏情况是数据元素已全部有序，此时数据元素数组的根结点的分需次数构成一棵二叉退化树(即单分支二叉树),一棵二叉退化树的深度是n,所以最坏情况下快速排序算法的时间复杂度为O(n2)。般情况下 ,标准元素值的分布是随机的，数组的分邮大数构成模二又树，这样的二叉树的深度接近于log2n, 所以快速排序算法的平均(或称期望）时间复杂度为O(nlog2n)
function findKey(&$arr, $low, $hight) { $target = $arr[$low]; while ($low < $hight) { while ($low < $hight && $target < $arr[$hight]) { $hight--; } $arr[$low] = $arr[$hight]; while ($low < $hight && $target > $arr[$low]) { $low++; } $arr[$hight] = $arr[$low]; } $arr[$hight]=$target; return $hight; } function quickSort(&$arr,$low,$hight){ $posKey=findKey($arr,$low,$hight); if($low<$posKey){ quickSort($arr,$low,$posKey-1); } if($posKey<$hight){ quickSort($arr,$posKey+1,$hight); } } $arr = [12, 56, 98, 32, 16, 34, 2, 9, 1]; $len = count($arr); quickSort($arr, 0, $len - 1); var_dump($arr);die;
原文：https://www.cnblogs.com/friendwrite/p/10393255.html