漫畫：什麼是快速排序？

————— 第二天 —————

————————————

同冒泡排序（什麼是冒泡排序？）一樣，快速排序也屬於交換排序，通過元素之間的比較和交換位置來達到排序的目的。

不同的是，冒泡排序在每一輪只把一個元素冒泡到數列的一端，而快速排序在每一輪挑選一個基準元素，並讓其他比它大的元素移動到數列一邊，比它小的元素移動到數列的另一邊，從而把數列拆解成了兩個部分。

這種思路就叫做分治法。

每次把數列分成兩部分，究竟有什麼好處呢？

假如給定8個元素的數列，一般情況下冒泡排序需要比較8輪，每輪把一個元素移動到數列一端，時間複雜度是O（n^2）。

而快速排序的流程是什麼樣子呢？

如圖所示，在分治法的思想下，原數列在每一輪被拆分成兩部分，每一部分在下一輪又分別被拆分成兩部分，直到不可再分為止。

這樣一共需要多少輪呢？平均情況下需要logn輪，因此快速排序演算法的平均時間複雜度是O（nlogn）。

基準元素的選擇

基準元素，英文Pivot，用於在分治過程中以此為中心，把其他元素移動到基準元素的左右兩邊。

那麼基準元素如何選擇呢？

最簡單的方式是選擇數列的第一個元素：

這種選擇在絕大多數情況是沒有問題的。但是，假如有一個原本逆序的數列，期望排序成順序數列，那麼會出現什麼情況呢？

..........

我們該怎麼避免這種情況發生呢？

其實很簡單，我們可以不選擇數列的第一個元素，而是隨機選擇一個元素作為基準元素。

這樣一來，即使在數列完全逆序的情況下，也可以有效地將數列分成兩部分。

當然，即使是隨機選擇基準元素，每一次也有極小的幾率選到數列的最大值或最小值，同樣會影響到分治的效果。

所以，快速排序的平均時間複雜度是O（nlogn），最壞情況下的時間複雜度是O（n^2）。

元素的移動

選定了基準元素以後，我們要做的就是把其他元素當中小於基準元素的都移動到基準元素一邊，大於基準元素的都移動到基準元素另一邊。

具體如何實現呢？有兩種方法：

挖坑法；

指針交換法。

挖坑法

何謂挖坑法？我們來看一看詳細過程。

給定原始數列如下，要求從小到大排序：

首先，我們選定基準元素Pivot，並記住這個位置index，這個位置相當於一個「坑」。並且設置兩個指針left和right，指向數列的最左和最右兩個元素：

接下來，從right指針開始，把指針所指向的元素和基準元素做比較。如果比Pivot大，則right指針向左移動；如果比Pivot小，則把right所指向的元素填入坑中。

在當前數列中，1

此時，left左邊綠色的區域代表著小於基準元素的區域。

接下來，我們切換到left指針進行比較。如果left指向的元素小於Pivot，則left指針向右移動；如果元素大於Pivot，則把left指向的元素填入坑中。

在當前數列中，7>4，所以把7填入index的位置。這時候元素7本來的位置成為了新的坑。同時，right向左移動一位。

此時，right右邊橙色的區域代表著大於基準元素的區域。

下面按照剛才的思路繼續排序：

8>4，元素位置不變，right左移。

2

6>4，用6來填坑，right左移，切換到right。

3

5>4，用5來填坑，right右移。這時候left和right重合在了同一位置。

這時候，把之前的Pivot元素，也就是4放到index的位置。此時數列左邊的元素都小於4，數列右邊的元素都大於4，這一輪交換終告結束。

public class QuickSort {

}

代碼中，quickSort方法通過遞歸的方式，實現了分而治之的思想。

partition方法則實現元素的移動，讓數列中的元素依據自身大小，分別移動到基準元素的左右兩邊。在這裡，我們使用的移動方式是挖坑法。

指針交換法

何謂指針交換法？我們來看一看詳細過程。

給定原始數列如下，要求從小到大排序：

開局和挖坑法相似，我們首先選定基準元素Pivot，並且設置兩個指針left和right，指向數列的最左和最右兩個元素：

接下來是第一次循環，從right指針開始，把指針所指向的元素和基準元素做比較。如果大於等於Pivot，則指針向左移動；如果小於Pivot，則right指針停止移動，切換到left指針。

在當前數列中，1

輪到left指針行動，把指針所指向的元素和基準元素做比較。如果小於等於Pivot，則指針向右移動；如果大於Pivot，則left指針停止移動。

由於left一開始指向的是基準元素，判斷肯定相等，所以left右移一位。

由於7 > 4，left指針在元素7的位置停下。這時候，我們讓left和right指向的元素進行交換。

接下來，我們進入第二次循環，重新切換到right向左移動。right先移動到8，8>4，繼續左移。由於2

切換到left，6>4，停止在6的位置。

元素6和2交換。

進入第三次循環，right移動到元素3停止，left移動到元素5停止。

元素5和3交換。

進入第四次循環，right移動到元素3停止，這時候請注意，left和right指針已經重合在了一起。

當left和right指針重合之時，我們讓Pivot元素和left與right重合點的元素進行交換。此時數列左邊的元素都小於4，數列右邊的元素都大於4，這一輪交換終告結束。

public class QuickSort {

}

和挖坑法相比，指針交換法在partition方法中進行的元素交換次數更少。

非遞歸實現

為什麼這樣說呢？

因為我們代碼中一層一層的方法調用，本身就是一個函數棧。每次進入一個新方法，就相當於入棧；每次有方法返回，就相當於出棧。

所以，我們可以把原本的遞歸實現轉化成一個棧的實現，在棧當中存儲每一次方法調用的參數：

下面我們來看一下代碼：

public class QuickSortWithStack {

}

和剛才的遞歸實現相比，代碼的變動僅僅在quickSort方法當中。該方法中引入了一個存儲Map類型元素的棧，用於存儲每一次交換時的起始下標和結束下標。

每一次循環，都會讓棧頂元素出棧，進行排序，並且按照基準元素的位置分成左右兩部分，左右兩部分再分別入棧。當棧為空時，說明排序已經完畢，退出循環。

本漫畫純屬娛樂，還請大家盡量珍惜當下的工作，切勿模仿小灰的行為哦。

聲明：本文為作者投稿，首發於個人公眾號程序員小灰，版權歸其所有。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！