PHP快速排序及其时间复杂度

时间：2021-11-06 09:40:51
<?php

function quickSort(&$arr, $l, $r)

{

    if (count($arr)<2 || $l>$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 即原数组有序时

相关文章