本帖为了快速牢靠的记住四种排序。
冒泡排序
冒泡排序的时间复杂度是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];
function po(&$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;
}
function qs(&$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];
function gui($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;
}
function bin($left, $right){
$arrC = array();
while(count($left) && count($right)){
$arrC[] = $left['0'] < $right['0'] ? array_shift($left) : array_shift($right);
}
return array_merge($arrC, $left, $right);
}
var_dump(gui($arr));其中，快速排序和归并排序都用到了递归，所以时间复杂度减少，但难度增大很多。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
