快速排序是由東尼霍爾所發(fā)展的一種排序算法。在平均n個(gè)項(xiàng)目要Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)。

快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來(lái)看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。

算法步驟：

從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）;

重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；

遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序

具體實(shí)現(xiàn)有兩種方法：

挖坑法

指針交換法

挖坑法

給定一組原始數(shù)列，要求從小到大排序：

首先，我們選定基準(zhǔn)元素Pivot，并記住這個(gè)位置index，這個(gè)位置相當(dāng)于一個(gè)“坑”。并且設(shè)置兩個(gè)指針left和right，指向數(shù)列的最左和最右兩個(gè)元素：

接下來(lái)，從right指針開始，把指針?biāo)赶虻脑睾突鶞?zhǔn)元素做比較。如果比pivot大，則right指針向左移動(dòng)；如果比pivot小，則把right所指向的元素填入坑中。

在當(dāng)前數(shù)列中，1<4，所以把1填入基準(zhǔn)元素所在位置，也就是坑的位置。這時(shí)候，元素1本來(lái)所在的位置成為了新的坑。同時(shí)，left向右移動(dòng)一位。

此時(shí)，left左邊綠色的區(qū)域代表著小于基準(zhǔn)元素的區(qū)域。

接下來(lái)，我們切換到left指針進(jìn)行比較。如果left指向的元素小于pivot，則left指針向右移動(dòng)；如果元素大于pivot，則把left指向的元素填入坑中。

在當(dāng)前數(shù)列中，7>4，所以把7填入index的位置。這時(shí)候元素7本來(lái)的位置成為了新的坑。同時(shí)，right向左移動(dòng)一位。

此時(shí)，right右邊橙色的區(qū)域代表著大于基準(zhǔn)元素的區(qū)域。

下面按照剛才的思路繼續(xù)排序：

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

2<4，用2來(lái)填坑，left右移，切換到left。

6>4，用6來(lái)填坑，right左移，切換到right。

3<4，用3來(lái)填坑，left右移，切換到left。

5>4，用5來(lái)填坑，right右移。這時(shí)候left和right重合在了同一位置。

這時(shí)候，把之前的pivot元素，也就是4放到index的位置。此時(shí)數(shù)列左邊的元素都小于4，數(shù)列右邊的元素都大于4，這一輪交換終告結(jié)束。

指針交換法：

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

開局和挖坑法相似，我們首先選定基準(zhǔn)元素Pivot，并且設(shè)置兩個(gè)指針left和right，指向數(shù)列的最左和最右兩個(gè)元素：

接下來(lái)是第一次循環(huán)，從right指針開始，把指針?biāo)赶虻脑睾突鶞?zhǔn)元素做比較。如果大于等于pivot，則指針向左移動(dòng)；如果小于pivot，則right指針停止移動(dòng)，切換到left指針。

在當(dāng)前數(shù)列中，1<4，所以right直接停止移動(dòng)，換到left指針，進(jìn)行下一步行動(dòng)。

輪到left指針行動(dòng)，把指針?biāo)赶虻脑睾突鶞?zhǔn)元素做比較。如果小于等于pivot，則指針向右移動(dòng)；如果大于pivot，則left指針停止移動(dòng)。

由于left一開始指向的是基準(zhǔn)元素，判斷肯定相等，所以left右移一位。

由于7 > 4，left指針在元素7的位置停下。這時(shí)候，我們讓left和right指向的元素進(jìn)行交換。

接下來(lái)，我們進(jìn)入第二次循環(huán)，重新切換到right向左移動(dòng)。right先移動(dòng)到8，8>2，繼續(xù)左移。由于2<8，停止在2的位置。

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

元素6和2交換。

進(jìn)入第三次循環(huán)，right移動(dòng)到元素3停止，left移動(dòng)到元素5停止。

元素5和3交換。

進(jìn)入第四次循環(huán)，right移動(dòng)到元素3停止，這時(shí)候請(qǐng)注意，left和right指針已經(jīng)重合在了一起。

當(dāng)left和right指針重合之時(shí)，我們讓pivot元素和left與right重合點(diǎn)的元素進(jìn)行交換。此時(shí)數(shù)列左邊的元素都小于4，數(shù)列右邊的元素都大于4，這一輪交換終告結(jié)束。

代碼實(shí)現(xiàn)：

總結(jié)

以上是生活随笔為你收集整理的实现快速排序的算法_排序算法-快速排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。