快速排序的簡單理解
詳細描述
快速排序通過一趟排序將待排序列分割成獨立的兩部分，其中一部分序列的關鍵字均比另一部分序列的關鍵字小，則可分別對這兩部分序列繼續進行排序，以達到整個序列有序的目的。
快速排序詳細的執行步驟如下：
- 從序列中挑出一個元素，稱為 「基準」（pivot）；
- 重新排序序列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於序列的中間位置。這個稱為分區（partition）操作；
- 遞歸地（recursive）把小於基準值元素的子序列和大於基準值元素的子序列排序。
演算法圖解
問題解疑
快速排序可以怎樣選擇基準值？
第一種方式：固定位置選擇基準值；在整個序列已經趨於有序的情況下，效率很低。
第二種方式：隨機選取待排序列中任意一個數作為基準值；當該序列趨於有序時，能夠讓效率提高，但在整個序列數全部相等的時候，隨機快排的效率依然很低。
第三種方式：從區間的首、尾、中間，分別取出一個數，然後對比大小，取這 3 個數的中間值作為基準值；這種方式解決了很多特殊的問題，但對於有很多重複值的序列，效果依然不好。
快速排序有什麼好的優化方法？
首先，合理選擇基準值，將固定位置選擇基準值改成三點取中法，可以解決很多特殊的情況，實現更快地分區。
其次，當待排序序列的長度分割到一定大小後，使用插入排序。對於待排序的序列長度很小或基本趨於有序時，插入排序的效率更好。
在排序後，可以將與基準值相等的數放在一起，在下次分割時可以不考慮這些數。對於解決重複數據較多的情況非常有用。
在實現上，遞歸實現的快速排序在函數尾部有兩次遞歸操作，可以對其使用尾遞歸優化（簡單地說，就是尾位置調用自身）。
程式碼實現
package cn.fatedeity.algorithm.sort;
import java.util.Random;
/**
* 快速排序演算法
*/
public class QuickSort {
private static void swap(int[] numbers, int src, int target) {
int temp = numbers[src];
numbers[src] = numbers[target];
numbers[target] = temp;
}
private static int[] sort(int[] numbers, int low, int high) {
if (low > high) {
return numbers;
}
// 隨機數取基準值
Random random = new Random();
int pivotIndex = random.nextInt(low, high + 1);
int pivot = numbers[pivotIndex];
swap(numbers, pivotIndex, low);
int mid = low + 1;
for (int i = low + 1; i <= high; i++) {
if (numbers[i] < pivot) {
swap(numbers, i, mid);
mid++;
}
}
swap(numbers, low, --mid);
sort(numbers, low, mid - 1);
sort(numbers, mid + 1, high);
return numbers;
}
public static int[] sort(int[] numbers) {
return sort(numbers, 0, numbers.length - 1);
}
}
