陳新龍

排序算法我們之前已經(jīng)講過了冒泡排序和選擇排序，今天我們就來學(xué)習(xí)一種新的排序算法：快速排序?？焖倥判蚴敲芭菖判虻母倪M(jìn)版本，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩個(gè)部分，其中一部分的所有數(shù)據(jù)要比另外一部分的所有數(shù)據(jù)小，然后按此方法對(duì)兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

首先我們將排序的元素進(jìn)行分區(qū)，從排序的元素中設(shè)置一個(gè)基準(zhǔn)（基準(zhǔn)可以任意設(shè)置，但是基本上都是把第一個(gè)數(shù)字設(shè)置為基準(zhǔn)），比基準(zhǔn)大的元素放在右邊，比基準(zhǔn)小的元素放在左邊，將左右兩個(gè)分區(qū)重復(fù)以上步驟直到所有元素都是有序的。所以我們可以把快速排序聯(lián)想成東拆西補(bǔ)或者西拆東補(bǔ)，一邊拆一邊補(bǔ)，直到所有的元素都達(dá)到有序的狀態(tài)。

待排序元素初始狀態(tài)：

把5作為與其他元素比較的基準(zhǔn)元素，設(shè)置兩個(gè)指針left和right。

1. 把5拆到一邊作為基準(zhǔn)元素（第二行數(shù)字為元素的初始狀態(tài)）;

2. right指針從右向左掃描，首先4和5比較，4<5，拆4，補(bǔ)原元素5的空缺位，left指針右移;

3. 7和5比較，7>5，拆7補(bǔ)元素4的空缺位。right指針左移;

4. 8和5比較，8>5，保持不變，right指針繼續(xù)左移;

5. 5和1比較，1<5補(bǔ)元素7的空缺位，left指針右移，此時(shí)left=right，則將基準(zhǔn)元素5補(bǔ)入到left/right的位置，結(jié)束這一趟拆補(bǔ)過程。

Python代碼部分：

第一步：在代碼中我們先增加一條需要排序的數(shù)列example。并且設(shè)置a：為起始位置，b：為末尾位置，接下來開始快速排序定義，head相當(dāng)于左指針，left相當(dāng)于右指針，base為基準(zhǔn)數(shù)。

第二步：從右往左掃描，通過偏移right指針，尋找比基準(zhǔn)數(shù)小的元素，當(dāng)找到比基準(zhǔn)數(shù)小的元素后，將其賦值給left指針?biāo)诘奈恢谩?p>

第三步：從左向右掃描，通過偏移left指針，尋找比基準(zhǔn)數(shù)大的元素，找到后，將其賦值right指針?biāo)赶虻奈恢谩?/p>

第四步：不斷重復(fù)二三步驟，直到left和right指針重合，這樣所有的元素都被掃描一遍了，將基準(zhǔn)數(shù)賦予重合位置，完成一遍排序，左邊的數(shù)字比基準(zhǔn)數(shù)小，右邊數(shù)字比基準(zhǔn)數(shù)大。

第五步：以之前的基準(zhǔn)數(shù)為分割點(diǎn)，對(duì)左右兩側(cè)按照以上的方法進(jìn)行遞歸，最后排序結(jié)束。

快速排序的效率雖然比冒泡排序高，但是它是一種不穩(wěn)定排序法：在一組數(shù)據(jù)中原有A1和A2兩個(gè)相等數(shù)字，不穩(wěn)定排序算法排序后，可能導(dǎo)致排序之后A2反而在A1之前，原有順序顛倒，這就稱為不穩(wěn)定排序。