本帖为了快速牢靠的记住四种排序。


冒泡排序

冒泡排序的时间复杂度是O(n^2);

外层控制趟数，并且跟内层排序个数相关。

$arr=[1,5,4,9,11];$n=count($arr);$max=$n-1;for($i=0;$i<$max;$i++){for($j=0;$j<$max-$i;$j++){if($arr[$j]>$arr[$j+1]){$t=$arr[$j];$arr[$j]=$arr[$j+1];$arr[$j+1]=$t;}}}var_dump($arr);


选择排序

选择排序的时间复杂度是O(n^2);

$arr=[1,5,4,9,11];$n=count($arr)-1;for($i=0;$i<$n;$i++){$t=$i;for($j=$i+1;$j<$n+1;$j++){if($arr[$t]>$arr[$j]){$t=$j;}}if($i!=$t){$tmp=$arr[$i];$arr[$i]=$arr[$t];$arr[$t]=$tmp;}}var_dump($arr);


快速排序

快速排序的时间复杂度是O(nlog2^n);

$arr=[16,2,5,6,19,8,10,30];functionpo(&$arr,$left,$right){$key=$arr[$left];while($left<$right){while($left<$right&&$arr[$right]>=$key){$right--;}if($left<$right){$arr[$left++]=$arr[$right];}while($left<$right&&$arr[$left]<=$key){$left++;}if($left<$right){$arr[$right--]=$arr[$left];}}$arr[$left]=$key;return$left;}functionqs(&$arr,$left,$right){if($left>=$right){return;}$i=po($arr,$left,$right);qs($arr,$left,$i-1);qs($arr,$i+1,$right);}qs($arr,0,7);var_dump($arr);


归并排序

归并排序的时间复杂度O(nlog2^n);

$arr=[9,7,11,3,5,8,39,4];functiongui($arr){$n=count($arr);if($n<=1){return$arr;}$mid=intval($n/2);$left=array_slice($arr,0,$mid);$right=array_slice($arr,$mid);$left=gui($left);$right=gui($right);$all=bin($left,$right);return$all;}functionbin($left,$right){$arrC=array();while(count($left)&&count($right)){$arrC[]=$left['0']<$right['0']?array_shift($left):array_shift($right);}returnarray_merge($arrC,$left,$right);}var_dump(gui($arr));


其中，快速排序和归并排序都用到了递归，所以时间复杂度减少，但难度增大很多。