快速排序演算法分析解析
快速排序演算法的時間複雜度和各次標準資料元素的值關係很大。如果每次選取的標準元素都能均分兩個子陣列的長度,這樣的快速排序過程是一個完全二叉樹結構。(即每個結點都把當前陣列分成兩個大小相等的陣列結點,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;