本帖为了快速牢靠的记住四种排序。
冒泡排序
冒泡排序的时间复杂度是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));其中，快速排序和归并排序都用到了递归，所以时间复杂度减少，但难度增大很多。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
