本帖為了快速牢靠的記住四種排序。

專業(yè)領(lǐng)域包括做網(wǎng)站、網(wǎng)站建設(shè)、商城網(wǎng)站制作、微信營(yíng)銷、系統(tǒng)平臺(tái)開發(fā)， 與其他網(wǎng)站設(shè)計(jì)及系統(tǒng)開發(fā)公司不同，創(chuàng)新互聯(lián)公司的整合解決方案結(jié)合了幫做網(wǎng)絡(luò)品牌建設(shè)經(jīng)驗(yàn)和互聯(lián)網(wǎng)整合營(yíng)銷的理念，并將策略和執(zhí)行緊密結(jié)合，為客戶提供全網(wǎng)互聯(lián)網(wǎng)整合方案。

冒泡排序

冒泡排序的時(shí)間復(fù)雜度是O(n^2);

外層控制趟數(shù)，并且跟內(nèi)層排序個(gè)數(shù)相關(guān)。

$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);

選擇排序

選擇排序的時(shí)間復(fù)雜度是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);

快速排序

快速排序的時(shí)間復(fù)雜度是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);

歸并排序

歸并排序的時(shí)間復(fù)雜度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));

其中，快速排序和歸并排序都用到了遞歸，所以時(shí)間復(fù)雜度減少，但難度增大很多。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

文章題目：我總結(jié)的四種排序-創(chuàng)新互聯(lián)
文章來(lái)源：http://weahome.cn/article/dpsehp.html