我总结的四种排序
本帖为了快速牢靠的记住四种排序。
冒泡排序
冒泡排序的时间复杂度是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));
其中,快速排序和归并排序都用到了递归,所以时间复杂度减少,但难度增大很多。
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。