Python快速排序

陳新龍

排序算法我們之前已經(jīng)講過了冒泡排序和選擇排序，今天我們就來學習一種新的排序算法：快速排序。快速排序是冒泡排序的改進版本，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩個部分，其中一部分的所有數(shù)據(jù)要比另外一部分的所有數(shù)據(jù)小，然后按此方法對兩部分數(shù)據(jù)分別進行快速排序，整個過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

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

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

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

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

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

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

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

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

Python代碼部分：

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

第二步：從右往左掃描，通過偏移right指針，尋找比基準數(shù)小的元素，當找到比基準數(shù)小的元素后，將其賦值給left指針所在的位置。

第三步：從左向右掃描，通過偏移left指針，尋找比基準數(shù)大的元素，找到后，將其賦值right指針所指向的位置。

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

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

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