我总结的四种排序-创新互联

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

专业领域包括做网站、网站建设、商城网站制作、微信营销、系统平台开发， 与其他网站设计及系统开发公司不同，创新互联公司的整合解决方案结合了帮做网络品牌建设经验和互联网整合营销的理念，并将策略和执行紧密结合，为客户提供全网互联网整合方案。

冒泡排序

冒泡排序的时间复杂度是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许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

网站名称：我总结的四种排序-创新互联
文章路径：http://cdiso.cn/article/dpsehp.html