|
快速排序法（Quick Sort）是劍橋大學(xué)教授在讀大學(xué)時發(fā)明的排序算法，也是當(dāng)今使用最廣泛的高效排序算法之一。QuickSort思路直觀而精巧，值得我們反復(fù)吟唱 算法動畫演示 
基本思想 對于從小到大排好序的數(shù)列中的任何一個元素，我們可以說： 這個數(shù)前面的所有數(shù)都不比它大 這個數(shù)后面的所有數(shù)都不比它小
反過來， 是不是也成立？ 對于序列中的一個數(shù)， 如果： 這個數(shù)前面的所有數(shù)都不比它大 這個數(shù)后面的所有數(shù)都不比它小
那么： 這個數(shù)已經(jīng)放在從小到大的升序數(shù)列中的最終的正確位置了。
快速排序法就是用這個直觀的事實來給數(shù)組中的每一個數(shù)字排序。 我們來看個例子： 現(xiàn)在有9個數(shù)字 [ 31 2 7 48 4 10 17 52 61 ], 我們?nèi)我膺x取一個數(shù)字17，下面來確定17的位置。 
17現(xiàn)在位于數(shù)組的第5位，也是整個數(shù)組排序后的最終位置：
在QuickSort中： 任意選取的這個數(shù)字（17）叫做“基準(zhǔn)”（pivot）。 所有元素比基準(zhǔn)pivot值小的擺放在基準(zhǔn)pivot前面，比基準(zhǔn)pivot值大的擺在基準(zhǔn)pivot的后面（相同的數(shù)可以到任一邊）。這樣該基準(zhǔn)pivot就處于數(shù)列的最終正確位置上。這個操作稱為分區(qū)（partition）
分區(qū)操作結(jié)束后，原來的數(shù)組被分割為2個小數(shù)組。 3 在這2個小數(shù)組上分別用遞歸（recursive）的辦法來重復(fù)同樣的操作（pivot， partition）。 
Partition算法實現(xiàn) 現(xiàn)在有長度為9的整數(shù)數(shù)組，我們選取第一個元素做為pivot。同時創(chuàng)建兩個“指針”變量，一個指向數(shù)組的頭，一個指向數(shù)組的尾巴。
j向左移動，直到遇到小于pivot(10)的數(shù)。 
把這個值（4）放到i指向的位置 
然后i向右移動，直到遇到大于pivot(10)的數(shù) 
把這個值（61）放到j指向的位置
反復(fù)重復(fù)以上1-4步驟，那么： i和j最后一定會相遇 i左邊的數(shù)字都比pivot(10)小 j右邊都數(shù)字都比pivot(10)大
那么：
沒有代碼的實現(xiàn)都是耍流氓 現(xiàn)在我們來看看代碼實現(xiàn)。先定義一個函數(shù)partition，然后聲明2個變量來記錄頭尾的位置， 同時聲明一個變量來記錄pivot的值。
下面是partition的邏輯：
從右到左移動“指針”變量j，找到第一個小于pivot的值
從左到右移動“指針”變量i，找到第一個大于pivot的值
最后來實現(xiàn)QuickSort的第3步：
在Partition后產(chǎn)生的2個小數(shù)組上分別用遞歸（recursive）的辦法來重復(fù)同樣的操作（pivot， partition）
算法復(fù)雜度 每次pivot-partition的時間復(fù)雜度為O(n). 逐漸遞歸劃分更小的范圍內(nèi)進(jìn)行pivot-partition。在最終排序完畢前，每次二分劃分，一共劃分了logn次，故快速排序時間復(fù)雜度為O(nlogn)。
這里我們來解釋一下為什么QuickSort比冒泡排序法快。 兩個算法都需要掃描整個數(shù)列來確定一個數(shù)據(jù)的最終位置。 但是冒泡排序法每次只能挑出最大的數(shù)字，放在最終的位置，而QuickSort不僅把pivot放到正確的位置，同時附帶按大小做了簡單的分類（比pivot小，比pivot大），每次掃描數(shù)列后保留了和排序有關(guān)的更多的信息。
算法系列： 10大常見排序算法（1） 冒泡
算法系列： 10大常見排序算法（2） 選擇排序
算法系列： 10大常見排序算法（3）插入排序
算法系列： 10大常見排序算法（4）希爾排序
|
