$r) return;    $tmp_l = $l;    $tmp_r = $r;    $privot = $arr[$r];    while($tmp_l<$tmp_r) {        while($arr[$tmp_l] < $privot && $tmp_l<$tmp_r) ++$tmp_l; //内部没有$tmp_l <$tmp_r的判断会造成$tmp_l > $tmp_r;  因为这里使用不是交换的方式，而是直接使用直接赋值的形式。            $arr[$tmp_r] = $arr[$tmp_l];        while($arr[$tmp_r] >= $privot && $tmp_l<$tmp_r) --$tmp_r; // 没有=等于的判断 会出现死循环，没有详细考究原因。            $arr[$tmp_l] = $arr[$tmp_r];    }    $arr[$tmp_l] = $privot;    quickSort($arr, $l, $tmp_l-1);    quickSort($arr, $tmp_r+1, $r);}$arr = array(3,4,4,4,6,7,8,9,3,3,4,2,5);print_r($arr);quickSort($arr, 0, count($arr)-1);print_r($arr);

 

时间复杂度为n*logn， 解释如下

假设每次都恰好把区间分成两段：

递归第一层有一个区间，长度N,1*N=N

第二层有两个区间，长度N/2,2*N/2=N

第三层有四个区间，长度N/4,4*N/4=N

....

第logN层有N个区间，长度1,N*1=N

所以，总共扫描过的长度是N*logN

 

最坏情况 logN = N 即原数组有序时