知識星球
精品專欄
速排序演演算法是最流行的排序演演算法，因為有充足的理由，在大多數情況下，快速排序都是最快的，執行時間為 O(NlogN) 級（這隻是對內部排序或者說隨機儲存器內的排序而言，對於在磁碟檔案中的資料進行的排序，其他的排序演演算法可能更好）。快速排序本質上透過一個陣列劃分為兩個子陣列，然後遞迴地呼叫自身為每一個子陣列進行快速排序來實現的，即演演算法分為三步：
-
1 把陣列或者子陣列劃分為左邊（較小的關鍵字）的一組和右邊（較大的關鍵字）的一組；
-
2 呼叫自身對左邊的一組進行排序；
-
3 呼叫自身對右邊的一組進行排序。
經過一次劃分之後，所有在左邊子陣列的資料項都小於在右邊子陣列的資料項，只要對左邊子陣列和右邊子陣列分別進行排序，整個陣列就是有序的了。下麵試一次劃分後的示意圖：
快速排序需要劃分陣列，這就用到了劃分演演算法。劃分演演算法是由兩個指標（這裡是指陣列資料項，非 C++ 中所說的指標）開始工作，兩個指標分別指向陣列的兩頭，左邊的指標 leftPtr 向右移動，右邊的指標 rightPtr 向左移動。當 leftPtr 遇到比樞紐（待比較的資料項，比其小的在其左邊，比其大的在其右邊，下麵均稱之為“樞紐”）小的資料項時繼續右移，當遇到比樞紐大的資料項時就停下來；類似的 rightPtr 想反。兩邊都停下後，leftPtr 和 rightPtr 都指在陣列的錯誤一方的位置的資料項，交換這兩個資料項。交換後繼續移動這兩個指標。
基於上面的劃分演演算法，可以將資料快速排好序，下麵是快速排序的實現程式碼：
public void quickSort(int[] a) {
recQuickSort(a,0, a.length-1);
}
public void recQuickSort(int[] a, int left, int right) {
if(right-left <= 0) {
return;
}
else {
int pivot = a[right]; //儲存最右邊的值，以這個值作為劃分點
int partition = partitionIt(a,left, right, pivot);//將陣列劃分兩部分，並將劃分點的值放在正確位置，並傳回該位置
recQuickSort(a, left, partition-1);//呼叫自身對左邊進行排序
recQuickSort(a, partition+1, right);//呼叫自身對右邊進行排序
}
}
public int partitionIt(int[] a, int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right;
while(true) {
while(a[++leftPtr] < pivot){} //往上找
while(rightPtr > 0 && a[--rightPtr] > pivot){} //往下找
if(leftPtr >= rightPtr) break;
else swap(leftPtr, rightPtr);
}
swap(leftPtr, right);//將劃分放在正確的位置
return leftPtr;//傳回劃分點，用於再次小範圍劃分
}
演演算法分析：快速排序是一種不穩定的排序方法，其平均時間複雜度為 O(NlogN)，最壞的情況下退化成插入排序了，為 O(N^2)。
快速排序是不穩定的，當 a=b>pivot 且 a 在 b 前面的時候，由於從後面開始遍歷，故 b 會先於 a 被替換到 pivot 的前面，這樣，b 就變成了在 a 的前面，也就是說，ab 位置對調，故該排序演演算法不穩定。
空間複雜度平均為 O(logN)，空間複雜度主要是由於遞迴造成的。
在理想狀態下應該選擇被排序的資料項的中值資料項作為樞紐（上面程式中是用陣列的最後一項作為樞紐的）。也就是說，應該有一半的資料項大於樞紐，一般的資料項小於樞紐。這會使陣列被劃分成兩個大小相等的子陣列。對於快速排序演演算法來說，擁有兩個大小相等的子陣列是最優的情況，最壞的情況就是一個子陣列只有一個資料項，另一個子陣列含有N-1個資料項。所以上面的演演算法中如果最右邊的資料是最小的或者最大的，那就可能導致最壞的情況出現。為瞭解決這個問題，我們可以改進上面的演演算法，使用“三資料項取中”劃分：找到陣列裡的第一個、最後一個以及中間位置資料項的值，將三個中處在中間大小的資料項作為樞紐，且將三個數排好序。下麵是改進的快速排序：
public void quickSort2(int[] a) {
recQuickSort2(a, 0, a.length-1);
}
public void recQuickSort2(int[] a, int left, int right) {
int size = right - left + 1;
if(size <= 3) {
manualSort(a, left, right);//資料項小於等於3個，直接排
}
else {
long median = medianOf3(a, left, right);//取左邊、右邊和中間三個數中中等大小的數作為樞紐
int partition = partitionIt2(a, left, right, median);//將樞紐放到正確的位置
recQuickSort2(a, left, partition-1);//呼叫自身對左邊進行排序
recQuickSort2(a, partition+1, right);//呼叫自身對右邊進行排序
}
}
private void manualSort(int[] a, int left, int right) {
int size = right - left + 1;
if(size <= 1) {
return; //1個不用排
}
if(size == 2) {
if(a[left] > a[right]) { //2個很好排
swap(left, right);
}
return;
}
else { //3個比較下就可以排好了
int center = right - 1;
if(a[left] > a[center]) {
swap(left, center);
}
if(a[left] > a[right]) {
swap(left, right);
}
if(a[center] > a[right]) {
swap(center, right);
}
}
}
private long medianOf3(int[] a, int left, int right) {
int center = (left + right) / 2;
if(a[left] > a[center]) {
swap(left, center);
}
if(a[left] > a[right]) {
swap(left, right);
}
if(a[center] > a[right]) {
swap(center, right);
}//已經將三個排好序
swap(center, right - 1); //然後將樞紐儲存在right-1位置
return a[right-1];//這保證了首位置比樞紐值小，最末尾位置比樞紐值大
}
public int partitionIt2(int[] a, int left, int right, long pivot) {
int leftPtr = left;
int rightPtr = right - 1;
while(true) {
while(a[++leftPtr] < pivot){} //往上找
while(a[--rightPtr] > pivot){} //往下找
if(leftPtr >= rightPtr) break;
else swap(leftPtr, rightPtr);
}
swap(leftPtr, right-1);//把right-1處存放的樞紐放到正確位置
return leftPtr;//傳回劃分點，用於再次小範圍劃分
}
演演算法分析：三資料項取中法除了對選擇樞紐更為有效外，還有另一個好處：可以對第二個內部 while 迴圈中取消 rightPtr>left（即 rightPtr>0）的測試，以略微提高演演算法的執行速度。因為在選擇的過程中使用三資料項取中法不僅選擇了樞紐，而且對這三個資料項進行了排序，所以就可以保證陣列最左端的資料項小於或者等於樞紐，最右端的資料項大於或者等於樞紐，所以就可以省去 rightPtr<0 的檢測了，leftPtr 和 rightPtr 不會分別越過陣列的最右端或者最左端。
三資料項取中還有一個小的好處是，對左端、中間以及右端的資料項排序後，劃分過程就不需要再考慮這三個資料項了，所以上面的程式中左端真正是從 left+1 處開始的，右端真正是從 right-2 處開始的（因為 right 處存的是比樞紐大的資料項，right-1 處存的是樞紐）。
如果使用三資料項取中劃分方法，則必須要遵循快速排序演演算法不能執行三個或者少於三個項的劃分規則。在這種情況下，數字3被稱為切割點(cutoff)。在上面的例子中，我們用一段程式碼手動對兩個或三個資料項的子陣列來排序的，但是這不是最好的方法。
處理小劃分的另一個選擇是使用插入排序。當使用插入排序的時候，不以限制3為切割點，可以把界限定位10、20或者其他任何數，試驗不同切割點的值找到最好的執行效率是很有意義的。最好的選擇值取決於計算機、作業系統、編譯器等。這裡使用9作為切割點。也就是說，當待比較的數小於等於9時，我們使用插入排序，大於9時我們使用快速排序法。繼續修改上面的程式：
public void quickSort3(int[] a) {
recQuickSort3(a, 0, a.length-1);
}
public void recQuickSort3(int[] a, int left, int right) {
int size = right - left + 1;
if(size < 10) {
insertionSort(a, left, right);//小於10項使用插入排序
}
else { //大於10項使用快速排序
long median = medianOf3(a, left, right);
int partition = partitionIt2(a, left, right, median);//上面的partionIt2方法
recQuickSort3(a, left, partition-1);
recQuickSort3(a, partition+1, right);
}
}
private void insertionSort(int[] a, int left, int right) {
for(int i = left + 1; i <= right; i++) {
for(int j = i; (j > left) && (a[j] < a[j-1]); j--) {
swap(j, j-1);
}
}
}
經過兩次改進後，這樣快速排序便結合了插入排序，三資料項取中法等方法，算是比較好的一個演演算法了。
你真的瞭解try{ return }finally{}中的return？
6 個實體詳解如何把 if-else 程式碼重構成高質量程式碼
END
>>>>>> 加群交流技術 <<<<<<