一、基本概念
找出一個元素（理論上可以隨便找一個）作為基準(pivot),然后對數組進行分區操作,使基準左邊元素的值都不大于基準值,基準右邊的元素值 都不小于基準值，如此作為基準的元素調整到排序后的正確位置。遞歸快速排序，將其他n-1個元素也調整到排序后的正確位置。最后每個元素都是在排序后的正 確位置，排序完成。所以快速排序算法的核心算法是分區操作，即如何調整基準的位置以及調整返回基準的最終位置以便分治遞歸。
二、選擇基準元
1、固定基準元
如果輸入序列是隨機的，處理時間是可以接受的。如果數組已經有序時，此時的分割就是一個非常不好的分割。因為每次劃分只能使待排序序列減一，此時為最壞情況，快速排序淪為冒泡排序，時間復雜度為Θ(n^2)。而且，輸入的數據是有序或部分有序的情況是相當常見的。因此，使用第一個元素作為基準元是非常糟糕的，應該立即放棄這種想法。
2、隨機基準元
這是一種相對安全的策略。由于基準元的位置是隨機的，那么產生的分割也不會總是會出現劣質的分割。在整個數組數字全相等時，仍然是最壞情況，時間復雜度是O(n^2）。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n）。所以隨機化快速排序可以對于絕大多數輸入數據達到O（n×log(n))的期望時間復雜度。
3、三數取中
最佳的劃分是將待排序的序列分成等長的子序列，最佳的狀態我們可以使用序列的中間的值，也就是第N/2個數。可是，這很難算出來，并且會明顯減慢快速排序的速度。這樣的中值的估計可以通過隨機選取三個元素并用它們的中值作為基準元而得到。事實上，隨機性并沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個元素的中值作為基準元。
三、partition算法
partition算法是快速排序的核心，在學習快排之前，可以先學習一下這個算法。下面先貼代碼:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public int partition(int[] num,int left,int right){ if(num==null || num.length<=0 || left<0 || right>=num.length){ return 0; } int prio=num[left+(right-left)/2]; //獲取數組中間元素的下標 while (left<=right){ //從兩端交替向中間掃描 while (num[left]<prio) left++; while (num[right]>prio) right--; if (left<=right){ swap(num,left,right); //最終將基準數歸位 left++; right--; } } return left;} |
這個方法的思路是先找一個樞紐元（這個方法實現里面找的是第一個元素，具體其實大有文章不過這里先簡化描述），再從數組的兩邊（具體從哪里到哪里由傳進來額參數決定）生成兩個指針left和right，每次發現左邊的元素大于樞紐元則i停下來，右邊的元素小于樞紐元j就停下來，并且交換這個兩個數的位置。直到兩個指針left，right相遇。再把樞紐元插入left的位置，也就是它應該在的位置。
這么做最后的結果是讓數組的[left，right]部分呈現出2部分，樞紐元最終位置以左都是小于等于樞紐元的，以右都是大于等于樞紐元的。而樞紐元則被插入到了一個絕對正確的位置。
四、排序算法實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
package sort;/** * 快速排序 * 快速排序采用了分治策略。就是在一個數組中取一個基準數字，把小的數放基準的左邊，大的數放基準的右邊。 * 基準左邊和右邊分別是新的序列。在新的序列中再取一個基準數字，小的放左邊，大的放右邊。 * 這個里面用到的遞歸。我們需要三個參數，一個是數組，另外兩個是序列的邊界 * @author HJS */public class QuickSort{ void sort(int num[],int left,int right){ if (left<right){ int index=partition(num,left,right); //算出樞軸值 sort(num,left,index-1); //對低子表遞歸排序 sort(num,index+1,right); //對高子表遞歸排序 } } /** * 調用partition(num,left,right)時，對num[]做劃分， * 并返回基準記錄的位置 * @param num * @param left * @param right * @return */ public int partition(int[] num,int left,int right){ if(num==null || num.length<=0 || left<0 || right>=num.length){ return 0; } int prio=num[left+(right-left)/2]; //獲取數組中間元素的下標 while (left<=right){ //從兩端交替向中間掃描 while (num[left]<prio) left++; while (num[right]>prio) right--; if (left<=right){ swap(num,left,right); //最終將基準數歸位 left++; right--; } } return left; } public void swap(int[] num,int left,int right){ int temp = num[left]; num[left] = num[right]; num[right] = temp; } public static void main(String args[]){ int[] num={7,3,5,1,2,8,9,2,6}; new QuickSort().sort(num,0,num.length-1); for(int n:num) { System.out.print(n+" "); } }} |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://www.cnblogs.com/jiansen/p/7343867.html
