學習數據結構時,書本上直接給出了快速排序的過程以及代碼,對其原理解釋的不夠詳細,琢磨代碼后,發現其原理其實十分簡單,簡述如下:
(1)在待排序列中找一個“中樞元素”(書本上默認取序列第一個元素)。
(2)通過操作,把比中樞元素大的數扔到中樞元素左邊,小的扔到右邊(假設要按降序排序)。
(3)將中樞元素左、右兩邊的子序列重復1,2過程。
(4)所有子序列長度為1時,排序結束。
那么怎么實現(2)中的“操作”呢?圖解如下:
假設序列為23,11,49,35,6,19.
我們用low和high分別指向第一個元素和最后一個元素,同時我們取第一個數23為“中樞元素”,將它“挖”出來,如下:
將23挖出來以后,最左邊就留下了一個“坑”,根據我們之前所說的,我們要把比中樞元素(23)大的扔到左邊,所以我們就要用high來找比23大的值,將它扔到之前在左邊挖好的坑里。現在,19比23小,19就不用動,因為我們本來就是要把比23小的數留在右邊。那么將high左移一位繼續,6也比23小,high再左移一位,發現35比23大,那么就把它填進左邊的坑里,如下:
此時high所指的位置也留下了一個坑,那么我們就用low在序列頭部開始找比23小的數來扔到右邊,35比23大,low右移一位,發現11比23小,所以將11填到右邊的坑里,如下:
繼續從high開始,往左找比23大的數,找到49,往左邊填坑,如下:
繼續從low開始,往右邊找,發現此時 low與high相遇了,那么這個地方就是中樞元素“歸位”的位置,如下:
好了,通過以上過程,我們已經將比23小的數扔到了右邊,大的數扔到了左邊。
此后,將以23為分界線的左右兩個子序列繼續重復此過程,直到所有子序列僅有一個元素為止,排序完成。