本文實例講述了java數據結構與算法之快速排序。分享給大家供大家參考，具體如下：
交換類排序的另一個方法，即快速排序。
快速排序：改變了冒泡排序中一次交換僅能消除一個逆序的局限性，是冒泡排序的一種改進；實現了一次交換可消除多個逆序。通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
步驟:
1、從數列中挑出一個元素，稱為 "基準"（pivot）；
2、重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
3、遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
算法實現代碼如下：
|
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
|
package exp_sort;public class QuickSort { public static void Qsort(int array[], int left, int right) { int pos; if (left < right) { pos = quickSort(array, left, right); //遞歸排序 Qsort(array, left, pos - 1); Qsort(array, pos + 1, right); } } /** * 一趟快速排序 * * @param array * @param left * @param right * @return */ public static int quickSort(int array[], int left, int right) { int low, high; int temp = array[left]; // 選擇基準記錄（樞紐元） low = left; high = right; while (low < high) { // high從右到左找小于temp的記錄 while (low < high && array[high] >= temp) { high--; } // 找到小于temp的記錄則交換 if (low < high) { array[low] = array[high]; low++; } // low從左到右找到大于temp的記錄 while (low < high && array[low] < temp) { low++; } // 找到大于temp的記錄，則交換 if (low < high) { array[high] = array[low]; high--; } } //將游標放在當前位置，此時low=high array[low] = temp; return low; } public static void main(String[] args) { // TODO Auto-generated method stub int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 }; Qsort(array, 0, 7); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println("\n"); }} |
樞紐元的選取：
1、基本的快速排序：選取地一個元素作為樞紐元。實際中應盡量避免將第一個元素作為樞紐元（極端情況是：初始狀態是已排好序或者反序的）。
2、隨機化快排序 : 隨機的選取樞紐元。
3、平衡快排 : 三數中值分割法：樞紐元的最好選擇是數組中的中值，該中值，即左端、右端和中心位置上的三個元素的中值（推薦）。
算法分析：該算法是在實踐中最快的一種排序算法，它的平均運行時間是O(N log N)，該算法之所以快，主要是由于非常精煉和高度優化的內部循環。它的最壞情況的性能是O(N^2)，但是這種情況可以改變。快速排序是一種分治的遞歸算法。該算法比歸并排序算法排序快。
1、最壞情況的分析
當樞紐元是最小元素時，此時就相當于是對整個數組進行遞歸排序，時間復雜度為：O(N^2)
2、最好情況的分析
樞紐元正好位于中間，此時是對兩個子數組進行遞歸排序，時間復雜度是：O(N log N)，這和歸并排序的分析完全相同。
3、平均情況的分析
時間復雜度是：O( N log N)
希望本文所述對大家java程序設計有所幫助。
