Python快速排序

陳新龍

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

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

待排序元素初始狀態：

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

1. 把5拆到一邊作為基準元素（第二行數字為元素的初始狀態）;

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

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

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

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

Python代碼部分：

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

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

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

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

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

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