4.6　快速排序算法

快速排序法又稱為分割交換法，是對冒泡排序法的一種改進。其基本思想是：先在數據中找一個虛擬的中間值，并按此中間值將打算排序的數據分為兩部分。其中，小于中間值的數據放在左邊，大于中間值的數據放在右邊；再用同樣的方式處理左右兩邊的數據，直到排序完成為止。

例如，有n項數據，數據值用K₁, K₂, …, K_n來表示。其快速排序法操作步驟如下：

（1）先在數據中假設一個虛擬中間值K（為了方便，一般取第一個位置上的數）。

（2）從左向右查找數據K_i，使得K_i>K，K_i的位置數記為i。

（3）從右向左查找數據K_j，使得K_j<K，K_j的位置數記為j。

（4）若i<j，數據K_i與K_j交換，并回到步驟（2）。

（5）若i≥j，數據K與K_j交換，并以j為基準點分割成左右兩部分，然后針對左右兩部分再進行步驟（1）～步驟（5），直到左半邊數據等于右半邊數據為止。

例如，有這樣一組數據：6, 1, 2, 7, 9, 3, 4, 5, 10, 8，如圖4.41所示。采用快速排序法遞增排序，步驟如下。

（1）取原始數列的第一個數6為虛擬中間值，即K=6；然后從左向右查找大于6的數，得到數字7，位置i=4；再從右向左查找小于6的數，得到數字5，位置j=8，如圖4.42所示。

（2）i<j，因此交換K_i（數字7）和K_j（數字5）的位置，完成第一次排序。繼續從左向右查找值大于6的數，即數字9，位置i=5；再從右向左查找值小于6的數，即數字4，位置j=7，如圖4.43所示。

（3）i<j，因此交換K_i（數字9）和K_j（數字4）的位置，完成第二次排序。繼續從左向右查找值大于6的數，即數字9，位置i=7；再從右向左查找值小于6的數，即數字3，位置j=6，如圖4.44所示。

（4）i>j，因此交換虛擬中間值K（數字6）和K_j（數字3）的位置，完成第三次排序。此時，發現6的左半邊都是小于6的數，右半邊都是大于6的數，虛擬中間值6變成了真正的中間值，如圖4.45所示。

（5）對中間值6左半邊的數據排序，中間值和右半邊數據暫時可以忽略。在左半邊取第一個位置的數為虛擬中間值，即K=3，從左向右查找大于3的值，即數字5，位置i=4；再從右向左查找小于3的值，即數字2，位置j=3，如圖4.46所示。

（6）i >j，因此需要交換虛擬中間值K（數字3）和K_j（數字2）的值，如圖4.47所示。此時虛擬中間值變成了真正的中間值。小于3的都在中間值3的左半邊，大于3的都在中間值3的右半邊。

（7）接下來對中間值3的左、右兩側排序，排序后的結果如圖4.48所示。

（8）此時，整組數據的左半邊已經完成排序，接下來需要忽略已排序好的左半邊和中間值6，對右半邊進行排序。取右半邊第一個位置的數為虛擬中間值，即K=9，然后從左向右找大于9的值，即數字10，位置i=9；再從右向左找小于9的值，即數字8，位置j=10，如圖4.49所示。

（9）i<j，因此交換K_i（數字10）和K_j（數字8）。然后再從左向右查找大于9的值，即為數字10，位置i=10；再從右向左找小于9的值，即為數字8，位置j=9，如圖4.50所示。

（10）i>j，因此交換虛擬中間值K（數字9）和K_j（數字8）的值，此時，虛擬中間值變成為真正的中間值，如圖4.51所示。

（11）以中間值9為界，分為左右兩側，再進行排序，最后完成右半邊排序，如圖4.52所示。

（12）結合左半邊排序和右半邊排序，最終的排序結果如圖4.53所示。

【實例4.11】　使用快速排序法將列表中的數字遞增排序。（實例位置：資源包\Code\04\11）

用Python代碼實現上方示例中的快速排序算法，具體代碼如下：

運行結果如圖4.54所示。

【實例4.12】　入職年限排名。（實例位置：資源包\Code\04\12）

例如，某公司的6名職員入職年限分別是1、3、15、20、5、4。利用快速排序法給這些職員入職年限從高到低順序排序，用Python實現具體代碼如下：

運行結果如圖4.55所示。