快速排序算法解析與實作

 每日一算法，今天我們來談談快速排序算法。為什麼叫它快速排序呢？因為它快呗。也許有人會笑，其實這裡說的也沒錯，目前的資料規模來看，它是最快的，而且是原址排序，就是不需要額外的空間來存放資料（歸并排序就是非原址的）。但是這裡要明确的是它的最壞時間複雜度确是O（n^2）。這個和堆排序還有歸并排序不一樣，它們即使最壞情況也是O（nlogn）。因為快速排序的平均時間複雜度是O(nlogn)，并且常數因子很小，是以它可以達到很快的速度。

  下面來看看快速排序的實作原理：

原理說明：可以看到，就是在資料集中，選擇任意一個元素key，然後将集合一分為二，左邊資料集是小于key，而右邊資料集是大于等于key的。

然後再分别對左右兩個資料集做遞歸處理，因為key的位置就是最終排序好的位置，是以遞歸結束後就全部排序好了！！！

這就是快速排序的基本思想。

     但是需要注意的是，key的選擇至關重要，它決定了排序的快慢。如果key選擇最大的元素或者最小的元素，就可能導緻分拆的最差情況，左邊是n-1個數，右邊是0個數。寫成遞歸公式則是T(n) = T(n-1) + O(n)。這個公式計算一下可以發現T(n)=O(n^2)。這是最糟糕的情況。當然，我們希望最好是兩邊數量均衡，為T(n) = 2*T(n/2) + O(n)的形式。但是一般很難達到，如果是事先進行過預排序後的資料，我們更不能随意選擇第一個或者最後一個作為key了。更好的做法是三元中位數法，簡單來說就是在資料中随意挑出三個資料，去中位數作為key，一般我們選擇第一個，最後一個，和中間一個來挑選中位數。

    這是用java實作的int[]快速排序算法：

<span style="font-size:18px;">package charp_1;


public class QuickSort {
	public static void main(String[] args)
	{
		int[] b = new int[]{10, 2, 3, 5, 7, 6, 100, 0, -3, 16};
		System.out.println("before quickSort:");
		print(b);
		quickSort(b);
		System.out.println("after quickSort:");
		print(b);
		
	}
	
	public static void print(int[] a)
	{
		for (int i = 0; i < a.length; i++) {
			System.out.printf("%d ", a[i]);
		}
		System.out.println();
	}
	
	public static void quickSort(int[] a)
	{
		subQuickSort(a, 0, a.length - 1);
	}
	
	private static void subQuickSort(int[] a, int p, int r)
	{
		if (p < r) {
			int q = partition(a, p, r);
			subQuickSort(a, p, q-1);
			subQuickSort(a, q+1, r);
		}
	}
	
	private static void swap(int[] a, int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	private static int partition(int[] a, int p, int r)
	{
		int key = a[r];
		int i = p - 1;
		for (int j = p; j < r; j++) {
			if (a[j] <= key) {
				i++;
				swap(a, i, j);
			}
		}
		swap(a, i+1, r);
		return i+1;
	}

	
}
</span>
           

運作的結果是：

細心的你會發現這裡我并沒有用剛剛提到的三元中位數法，是以這個算法很可能會在預處理資料面前變的不那麼高效！！！

我們可以将上面的partition函數換成下面的partition2函數：

<span style="font-size:18px;">	private static int partition2(int[] a, int p, int r)
	{
		int mid = (p + r) / 2;
		int med;
		if (a[p] <= a[mid] && a[mid] <= a[r])
			med = mid;
		else if (a[mid] <= a[p] && a[p] <= a[r])
			med = p;
		else {
			med = r;
		}
		int key = a[med];
		swap(a, med, r);
		int i = p - 1;
		for (int j = p; j < r; j++) {
			if (a[j] <= key) {
				i++;
				swap(a, i, j);
			}
		}
		swap(a, i+1, r);
		return i+1;
	}</span>
           

運作結果是一樣的，但是很顯然下面的算法會更高效一下。

既然用了java就不能寫這麼沒有擴充性的程式，起碼來個泛型快排吧，可以處理任意資料類型的數組！！！下面是泛型快排代碼：

<span style="font-size:18px;">/**
 * 
 */
package charp_1;


/**
 * @author freestyle458
 *
 */
public class QuickSort2 {
	public static void main(String[] args)
	{
		int[] b = new int[]{-17, 8, 100 ,6, 16, 1, 2, 78};
		Integer[] items = new Integer[b.length];
		for (int i = 0; i < items.length; i++)
			items[i] = b[i];
		System.out.println("before quickSort:");
		print(items);
		quickSort(items);
		System.out.println("after quickSort:");
		print(items);
	}
	
	public static <T extends Comparable<T>> void print(T[] items)
	{
		for (int i = 0; i < items.length; i++)
			System.out.printf(items[i] + " ");
		System.out.println();
	}
	
	public static <T extends Comparable<T>> void quickSort(T[] items)
	{
		subQuickSort(items, 0, items.length-1);
	}
	
	public static <T extends Comparable<T>> void subQuickSort(T[] items, int p, int r)
	{
		if (p < r) {
			int q = partition(items, p, r);
			subQuickSort(items, p, q-1);
			subQuickSort(items, q+1, r);
		}
	}
	
	private static <T extends Comparable<T>> void swap(T[] items, int i, int j)
	{
		T tmp = items[i];
		items[i] = items[j];
		items[j] = tmp;
	}
	
	private static <T extends Comparable<T>> int partition(T[] items, int p, int r)
	{
		int midIndex = (p+r)/2;
		int medIndex;
		if (items[p].compareTo(items[midIndex]) <= 0 &&
			items[midIndex].compareTo(items[r]) <= 0)
			medIndex = midIndex;
		else if (items[midIndex].compareTo(items[p]) <= 0 &&
				 items[p].compareTo(items[r]) <= 0)
			medIndex = p;
		else {
			medIndex = r;
		}
		
		swap(items, medIndex, r);
		
		int i = p - 1;
		T key = items[r];
		for (int j = p; j < r; j++) {
			if (items[j].compareTo(key) <= 0) {
				i++;
				swap(items, i, j);
			}
		} 
		swap(items, i+1, r);
		
		return i+1;
	}
	
}


</span>
           

運作結果是：

除了可以排序整數外，我們來試一下排序字元串看看：

<span style="font-size:18px;">	public static void main(String[] args)
	{
		String[] items = new String[]{"asdfdas", "wrb", "asdf", "ohnkh", "yexin"};
		System.out.println("before quickSort:");
		print(items);
		quickSort(items);
		System.out.println("after quickSort:");
		print(items);
	}</span>
           

其實快排思想很重要，在很多時候我們都可以借助快排思想來高效的完成一些工作，具體等到結合程式設計題目來看看吧！！

以一張快排趣圖結束：