上篇文章中我們好好地學(xué)習(xí)了一下插入類相關(guān)的兩個(gè)排序，不過(guò)，和交換類的排序?qū)Ρ鹊脑?，它們真的只是弟弟。甚至可以說(shuō)，在所有的排序算法中，最出名的兩個(gè)排序都在今天要介紹的交換排序中了。不管是冒泡、還是快排，都是面試中的常見排序算法，常見到什么地步呢？但凡學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法，甚至是你完全沒(méi)有學(xué)習(xí)過(guò)，也多少都會(huì)聽說(shuō)過(guò)這兩個(gè)排序算法。而一些大中型公司更是直接在面試題中指明不要使用這兩種算法來(lái)實(shí)現(xiàn)一些排序的題目，這又是為什么呢？那當(dāng)然也是因?yàn)檫@兩個(gè)算法實(shí)在是太出名了，很多人都隨便就能手寫出來(lái)。
當(dāng)然，不管你面試的公司有什么要求，只要是有志在編程開發(fā)這個(gè)行業(yè)里發(fā)展的同學(xué)，冒泡和快排肯定會(huì)是面試中繞不開的一個(gè)坎。我們今天就來(lái)好好地學(xué)習(xí)一下這兩個(gè)排序算法。不過(guò)首先還是要搞明白這個(gè)“交換”指的是什么意思。
上篇文章中的插入排序，指的是直接將數(shù)據(jù)插入到指定的位置。而交換的意思，則是讓兩個(gè)位置的數(shù)據(jù)在進(jìn)行比對(duì)后直接交換。比如我們有 [3, 1, 2] 這樣一個(gè)數(shù)組，需要排列成 [1, 2, 3] 這種形式。那么我們就可以先讓 3 和 1比較，發(fā)現(xiàn) 1 小，于是將 3 和 1 的位置進(jìn)行交換，結(jié)果是 [1, 3, 2] 。然后再讓 3 和 2 比較，發(fā)現(xiàn) 2 小，再交換它們的位置，于是得到結(jié)果為 [1, 2, 3] 的數(shù)組。
當(dāng)然，這個(gè)示例只是簡(jiǎn)單地說(shuō)明了一下交換排序的原理。但萬(wàn)變不離其宗，不管是冒泡還是快排，它們的基本原理和核心思想都是這樣的，讓兩個(gè)數(shù)據(jù)對(duì)比后根據(jù)規(guī)則交換位置。這里其實(shí)從代碼中我們能夠從一個(gè)地方很快地分辨出一段排序代碼是否是交換排序，那就是他們會(huì)有一個(gè)對(duì)于兩個(gè)元素進(jìn)行數(shù)據(jù)交換的過(guò)程，而且往往在普通情況下會(huì)使用一個(gè)中間變量。這個(gè)我們一會(huì)看代碼就可以看到。
冒泡排序，先從名字來(lái)理解一下，它的意思其實(shí)是讓數(shù)據(jù)像汽水中的泡泡一樣一個(gè)一個(gè)的浮上來(lái)。
直接上代碼了來(lái)看看，代碼其實(shí)非常簡(jiǎn)單。
function BubbleSort($numbers)
{
$n = count($numbers);
for ($i = 0; $i < $n - 1; $i++) { // 外層循環(huán) n - 1
for ($j = 0; $j < $n - $i - 1; $j++) { // 內(nèi)層循環(huán) n - 1 - i
if ($numbers[$j] > $numbers[$j + 1]) { // 兩兩相比來(lái)交換
$temp = $numbers[$j + 1];
$numbers[$j + 1] = $numbers[$j];
$numbers[$j] = $temp;
}
}
}
print_r($numbers);
}
BubbleSort($numbers);
// Array
// (
// [0] => 13
// [1] => 27
// [2] => 38
// [3] => 49
// [4] => 49
// [5] => 65
// [6] => 76
// [7] => 97
// )
光看代碼自己推演的話其實(shí)還是不太好理解，那么我們就還是使出終極殺器，也就是圖解步驟來(lái)看一下吧！
在代碼中可以看到，我們有兩層循環(huán)。所以這個(gè)圖片中我們也是展示了 i 和 j 的兩層循環(huán)情況。當(dāng)然，限于篇幅，我們只展示了第一次 i 循環(huán)內(nèi)部的 j 循環(huán)情況，也就是 i = 0 時(shí)，里面的 j 循環(huán)執(zhí)行的情況。
i = 0 是，內(nèi)部的 j < n - 1 - i ，也就是內(nèi)部的 j 要循環(huán)七次。我們直接就看右邊的 j 循環(huán)的步驟。
冒泡排序其實(shí)就是利用 j 和 j + 1 來(lái)對(duì)比兩個(gè)相鄰的元素。從圖中我們就可以看出，每一次 j++ 都是在對(duì)當(dāng)前 j 和下一個(gè) j + 1 的元素進(jìn)行比較。如果當(dāng)前的這個(gè) j 大于 j + 1 的話，就把它們交換位置。
當(dāng) j = 0 時(shí)，第 0 個(gè)位置的 49 是大于第 1 個(gè)位置的 38 的，于是 49 和 38 交換了位置。
當(dāng) j = 1 時(shí)，位置 1 的 49 和位置 2 的 65 相比，沒(méi)有達(dá)成條件，于是不會(huì)變動(dòng)。同理，j = 2 時(shí)也是對(duì)比的 65 和 97 ，同樣不會(huì)發(fā)生交換。
當(dāng) j = 3 時(shí)，97 比 76 要大，于是發(fā)生了交換，97 交換到 j + 1 也就是下標(biāo) 4 的位置。同時(shí)，97 也是整個(gè)序列中最大的數(shù)，于是后面會(huì)一直交換到這次的 j 循環(huán)結(jié)束。
最終的結(jié)果是 97 這個(gè)最大的數(shù)移動(dòng)到了數(shù)據(jù)的最后一位。也就是說(shuō)，最大的數(shù)已經(jīng)放到了整個(gè)序列中的正確的位置上了。
接著內(nèi)層循環(huán)結(jié)束，i++ ，開始第二次 i = 1 的內(nèi)部 j 循環(huán)。這里需要注意的是，為什么我們要用 j < n - 1 - i 呢？因?yàn)槲覀兦懊嬉呀?jīng)完成了一個(gè)最大數(shù)的排序，就是將 97 這個(gè)最大數(shù)放到了最后的位置上。所以在 i++ 的第二次循環(huán)時(shí)，我們就要將第二大的數(shù)放在倒數(shù)第二的位置上。這時(shí)的 j 也不需要循環(huán)到最后一位了，只需要循環(huán)到倒數(shù)第二位就可以了。
從上面的分步講解中，我們可以看到，外層的 i 每一次的循環(huán)其實(shí)就是通過(guò)內(nèi)層的 j 循環(huán)來(lái)將一個(gè)最大的數(shù)按順序放到后面的位置上。就像汽水不斷地向上冒泡一樣，它就是傳說(shuō)中的冒泡排序算法概念的由來(lái)。
其實(shí)關(guān)于冒泡排序的算法，還有一個(gè)口決是很多同學(xué)都知道的，也可以幫助我們記憶。
外層循環(huán) N 減一
內(nèi)層循環(huán) N 減一減 I
兩兩相比小靠前（正序）
為什么小的靠前是正序呢？在代碼中，我們 if 條件判斷是的 j > j+1 ，如果成立就交換它們，也就是讓大的數(shù)據(jù)放到了后面，小的數(shù)據(jù)放到了前面，這樣一輪過(guò)后，最大的數(shù)據(jù)放在了最后一位，也就是完成了一個(gè)最大數(shù)據(jù)的位置的確定。如果我們將條件反過(guò)來(lái)，也就是 j < j+1 的話，就會(huì)讓最大的數(shù)據(jù)放到最前面，也就是實(shí)現(xiàn)了倒序。是不是很神奇？小伙伴們可以試試哦，就改變一下 if 條件的大于號(hào)就可以了哦。
冒泡的時(shí)間復(fù)雜度其實(shí)很明顯地就能看出來(lái)，O(N2)。屬于效率一般但非常好理解的一種算法，而且它是一個(gè)穩(wěn)定的排序算法。
冒泡的感覺咋樣？不過(guò)冒泡有個(gè)問(wèn)題，那就是它只能對(duì)相鄰的兩個(gè)數(shù)據(jù)進(jìn)行比較，所以 O(N2) 這個(gè)時(shí)間復(fù)雜度基本也就不包含什么最好最壞的情況了，不管怎么它都得要達(dá)到這個(gè) O(N2) 的水平。
那么有沒(méi)有什么別的方法能夠?qū)γ芭葸M(jìn)行優(yōu)化呢？有大佬就發(fā)明出了優(yōu)化冒泡的一種排序算法啦。那就是快速排序算法。還記得在學(xué)習(xí)查找的時(shí)候我們學(xué)習(xí)過(guò)的二分查找嗎？相對(duì)于線性查找來(lái)說(shuō)，二分查找的效率是不是提升了很多。但快速排序的效率提升可達(dá)不到那么高，畢竟排序還是比查找要復(fù)雜些。而且它是在冒泡的基礎(chǔ)上進(jìn)行的改良，同樣也使用了二分的思想，也就是分而治之的一種理念。讓每次的比較不再只是兩個(gè)相鄰的元素一個(gè)一個(gè)地比較。所以它的平均時(shí)間復(fù)雜度可以提升到 O(NlogN) 的級(jí)別。相對(duì)于 O(N2) 來(lái)說(shuō)，這個(gè)時(shí)間復(fù)雜度其實(shí)也有了不小的飛躍哦。特別是數(shù)據(jù)量越大的情況下越明顯。
同樣我們先來(lái)看看代碼，然后再來(lái)看圖分析這個(gè)算法。
function QSort(&$arr, $start, $end)
{
if ($start > $end) {
return;
}
$key = $arr[$start];
$left = $start;
$right = $end;
while ($left < $right) {
// 右邊下標(biāo)確定
while ($left < $right && $arr[$right] >= $key) {
$right--;
}
// 左邊下標(biāo)確定
while ($left < $right && $arr[$left] <= $key) {
$left++;
}
if ($left < $right) { // 交換步驟
$tmp = $arr[$left];
$arr[$left] = $arr[$right];
$arr[$right] = $tmp;
}
}
$arr[$start] = $arr[$left];
$arr[$left] = $key;
// 遞歸左右兩邊繼續(xù)
QSort($arr, $start, $right - 1);
QSort($arr, $right + 1, $end);
}
function QuickSort($numbers)
{
QSort($numbers, 0, count($numbers) - 1);
print_r($numbers);
}
QuickSort($numbers);
// Array
// (
// [0] => 13
// [1] => 27
// [2] => 38
// [3] => 49
// [4] => 49
// [5] => 65
// [6] => 76
// [7] => 97
// )
有沒(méi)有發(fā)現(xiàn)熟悉的身影？沒(méi)錯(cuò)，快速排序使用到了遞歸。這個(gè)遞歸其實(shí)也包含著分治的思想，就像秦國(guó)統(tǒng)一六國(guó)一樣，分而治之。我們將某一個(gè)數(shù)據(jù)放到指定的位置之后再按左右分治的方式來(lái)繼續(xù)其它的數(shù)據(jù)的排序，而不用讓其它的數(shù)據(jù)再對(duì)整個(gè)序列進(jìn)行完整的判斷，從而提高排序的效率。因此，快排的時(shí)間復(fù)雜度相對(duì)冒泡來(lái)說(shuō)就好了很多。
同樣地，它表面上是不停地遞歸，其實(shí)遞歸也是一種循環(huán)，我們就可以看出來(lái)，它和冒泡一樣其實(shí)是有著兩層循環(huán)的概念的。這里我們也是以第一次的外層循環(huán)為例子來(lái)剖析它的內(nèi)層循環(huán)都做了什么。
首先，我們確定了一個(gè)關(guān)鍵字 key ，這里我們就直接指定第一個(gè)數(shù)據(jù) 49 。然后指定左右兩個(gè)指針，左指針 left 從 0 開始，右指針 right 從最右邊的下標(biāo)開始。
進(jìn)入內(nèi)層循環(huán)，條件是 left < right ，也就是左右兩個(gè)指針不能相遇！
開始指針移動(dòng)，先從右邊開始，如果 right 指向的數(shù)據(jù)大于等于 key ，right 就進(jìn)行減減操作，否則，指針就停住?？梢钥吹?，我們的指針停在了 27 這個(gè)數(shù)據(jù)的位置，也就是倒數(shù)第二個(gè)數(shù)據(jù)這里，第一個(gè)數(shù)據(jù) 49 和我們的 key 值 49 是一樣的，于是 right 就移動(dòng)到倒數(shù)第二個(gè)數(shù)據(jù)了，27 是小于 key 值的。
然后移動(dòng) left 指針，移動(dòng)到符合條件的位置也就是值為 65 的這個(gè)下標(biāo)，然后交換 left 和 right 的值。
繼續(xù)后續(xù)的操作，直到 left 和 right 相遇了，這時(shí)退出循環(huán)，并在循環(huán)外面再次交換 key 和 left 位置的值。這時(shí)，第一個(gè)下標(biāo)的 49 這個(gè)值就已經(jīng)放到了它所確定的位置。也就是說(shuō)，這個(gè)值完成了排序。
接著，以這個(gè)完成排序的值為中心，切分左右兩個(gè)序列，繼續(xù)進(jìn)入遞歸排序的過(guò)程，直到所有數(shù)據(jù)完成排序。
看出快速排序和冒泡排序的區(qū)別了吧？快排的每趟排序都會(huì)確定一個(gè)關(guān)鍵字的具體位置，它的比較除了第一次是每個(gè)數(shù)都和 key 兩兩比較之外，其它都是采用分治的思想來(lái)縮小 n 的大小進(jìn)行小范圍的排序的。而且每次的循環(huán)都會(huì)將數(shù)據(jù)按針對(duì) key 值的大小進(jìn)行左右排列，這也是二叉搜索樹的核心思想。這個(gè)內(nèi)容我們的系列文章中沒(méi)有講解，大家可以自行查閱相關(guān)的資料學(xué)習(xí)。
今天學(xué)習(xí)的內(nèi)容中都有一處核心的代碼，就是最開始我們說(shuō)過(guò)的交換兩個(gè)變量值的代碼。
// 冒泡中
$temp = $numbers[$j + 1];
$numbers[$j + 1] = $numbers[$j];
$numbers[$j] = $temp;
// 快排中
$tmp = $arr[$left];
$arr[$left] = $arr[$right];
$arr[$right] = $tmp;
我們都使用到了一個(gè)臨時(shí)變量來(lái)進(jìn)行交換。不過(guò)不少的面試題中經(jīng)常會(huì)看到一種題目就是不使用第三個(gè)變量，也就是這個(gè)臨時(shí)變量來(lái)交換兩個(gè)變量的值。大家有沒(méi)有踫到過(guò)呢？其實(shí)有幾種方案都可以，我們就來(lái)簡(jiǎn)單說(shuō)兩個(gè)。
$a = 1;
$b = 2;
$a += $b; // a = 3
$b = $a - $b; // b = 3 - 2 = 1
$a = $a - $b; // a = 3 - 1 = 2
echo $a, PHP_EOL; // 2
echo $b, PHP_EOL; // 1
$a = "a";
$b = "b";
$a .= $b; // a = "ab"
$b = str_replace($b, "", $a); // b = str_replace("b", "", "ab") = a
$a = str_replace($b, "", $a);// a = str_replace("a", "", "ab") = b
echo $a, PHP_EOL; // b
echo $b, PHP_EOL; // a
對(duì)于數(shù)字來(lái)說(shuō)，直接使用第一段的加減操作就可以完成兩個(gè)變量的交換。而對(duì)于字符串來(lái)說(shuō)，就可以使用 str_replace() 來(lái)實(shí)現(xiàn)。其實(shí)它們的思想都是一樣的，先合并到一個(gè)變量上，然后利用減法或者替換來(lái)讓某一個(gè)變量先變成另一個(gè)變量的值。然后再使用相同的方法將另一個(gè)變量的值也轉(zhuǎn)換成功。當(dāng)然，這只是最簡(jiǎn)單最基礎(chǔ)的一種算法，利用 PHP 的一些函數(shù)和特性，我們還可以更方便地實(shí)現(xiàn)這種功能。
$a = 1;
$b = 2;
list($a, $b) = [$b, $a];
echo $a, PHP_EOL; // 2
echo $b, PHP_EOL; // 1
list() 函數(shù)是將一個(gè)數(shù)組中的數(shù)據(jù)分別存入到指定的變量中，而在 PHP 中我們也可以直接 [x, x] 這樣來(lái)定義數(shù)組。所以不使用第三個(gè)臨時(shí)變量來(lái)交換兩個(gè)變量的功能我們只用這一行代碼就搞定了。list(b) = [a] 。這里不點(diǎn)贊可真對(duì)不起這道題咯?。?/p>
交換排序的這兩種算法相當(dāng)于數(shù)據(jù)結(jié)構(gòu)與算法這門課程的門面擔(dān)當(dāng)，但凡要講算法中的排序的，必然會(huì)有它們兩個(gè)的身影。畢竟太經(jīng)典了，不過(guò)我們可是先學(xué)了兩個(gè)插入類的排序進(jìn)行過(guò)了熱身才來(lái)學(xué)習(xí)這兩個(gè)經(jīng)典算法的，相信大家進(jìn)行對(duì)比之后就能更深入地理解這些算法的神奇和不同。
測(cè)試代碼：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/7.排序/source/7.2交換排序：冒泡、快排.php
參考文檔：
本文示例選自 《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏
《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越
聯(lián)系客服
