Like Share Discussion Bookmark Smile

J.J. Huang   2020-03-13   排序演算法   瀏覽次數:次   DMCA.com Protection Status

排序演算法 | 快速排序

快速排序(英語:Quicksort),又稱劃分交換排序(partition-exchange sort),簡稱快排,一種排序演算法,最早由東尼·霍爾提出。在平均狀況下,排序n個項目要O(n log n)(大O符號)次比較。在最壞狀況下則需要 O(n²)次比較,但這種狀況並不常見。事實上,快速排序 Θ(n log n)通常明顯比其他演算法更快,因為它的內部迴圈(inner loop)可以在大部分的架構上很有效率地達成。

快速排序使用分治法(Divide and conquer)策略來把一個序列(list)分為較小和較大的2個子序列,然後遞迴地排序兩個子序列。

步驟為:

  • 挑選基準值:從數列中挑出一個元素,稱為「基準」(pivot),
  • 分割:重新排序數列,所有比基準值小的元素擺放在基準前面,所有比基準值大的元素擺在基準後面(與基準值相等的數可以到任何一邊)。在這個分割結束之後,對基準值的排序就已經完成,
  • 遞迴排序子序列:遞迴地將小於基準值元素的子序列和大於基準值元素的子序列排序。

遞迴到最底部的判斷條件是數列的大小是零或一,此時該數列顯然已經有序。

選取基準值有數種具體方法,此選取方法對排序的時間效能有決定性影響。

使用快速排序法對一列數字進行排序的過程:

原地(In-place)分割版本的快速排序:

實作範例(Java)

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
60
61
62
63
64
65
66
67
68
69
70
public static void quickSort(int[] arr, int left, int right) {
int l = left; // 左下標
int r = right; // 右下標
int pivot = arr[(left + right) / 2]; // 找到中間的值
// 將比pivot小的值放在其左邊,比pivot大的值放在其右邊
while (l < r) {
// 在pivot左邊尋找,直至找到大於等於pivot的值才退出
while (arr[l] < pivot) {
l += 1; // 將l右移一位
}
// 在pivot右邊尋找,直至找到小於等於pivot的值才退出
while (arr[r] > pivot) {
r -= 1; // 將r左移一位
}
if (l >= r) {
// 左右下標重合,尋找完畢,退出循環
break;
}
// 交換元素
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;

//倘若發現值相等的情況,則沒有比較的必要,直接移動下標即可

// 如果交換完後,發現arr[l]==pivot,此時應將r左移一位
if (arr[l] == pivot) {
r -= 1;
}
// 如果交換完後,發現arr[r]==pivot,此時應將l右移一位
if (arr[r] == pivot) {
l += 1;
}
}
// 如果l==r,要把這兩個下標錯開,否則會出現無限遞歸,導致棧溢出的情況
if (l == r) {
l += 1;
r -= 1;
}
// 向左遞歸
if (left < r) {
quickSort(arr, left, r);
}
// 向右遞歸
if (right > l) {
quickSort(arr, l, right);
}
}

public static void main(String[] args) {
int[] arr = {
3,
44,
38,
5,
47,
15,
36,
26,
27,
2,
46,
4,
19,
50,
48
};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}

結果:

1
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

快速排序的實現原理很簡單,就是將原數組分成兩部分,然後以中間值為標準,比它小的就放其左邊,比它大的就放其右邊,然後在左右兩邊又以相同的方式繼續排序。
所以在代碼實現過程中,首先要創建兩個移動的變量,一個從最左邊開始往右移動,一個從最右邊開始往左移動,通過這兩個變量來遍歷左右兩部分的元素。當發現左邊有大於中間數的元素,右邊有小於中間數的元素,此時就進行交換。當兩個變量重合也就是相等的時候遍歷結束,然後左右兩部分作遞歸處理。


註:以上參考了
維基百科-快速排序
演算法筆記
程式员必须掌握的核心算法有哪些?
程式员那些必须掌握的排序算法(上)
程式员那些必须掌握的排序算法(下)