partition（劃分）是quick sort的主要概念。 將陣列根據一個pivot（基準點），將陣列劃分成兩個部分，分別是：比該基準點左邊的，跟比該基準點右邊的。
let pivot = 3 // 陣列中第3個為基準點
[A,B,C,D,E,F,G]
^基準點
[A,B,C] [D] [E,F,G]
左半部 基準點 右半部
根據一個pivot（基準點），判斷陣列中其他元素是比這個基準點大還是比較小，然後調整陣列，使得「所有在pivot左邊的數，都比pivot還小」，而「在pivot右邊的數都比pivot大」。
接著，將所有在pivot左邊的數視為「新陣列」，所有在pivot右邊的數視為「另一個新陣列」，各自重複上述步驟(選pivot、調整陣列)，直到分不出「新陣列」為止。
假設陣列[5, 7, 13, 7, 4, 8]，假設基準點為index為最後一個的元素，並從該基準點的最左邊開始跟基準點的值比較大小。箭頭j代表正在被比較的元素，i代表「目前有幾個值比基準點小」：
index 0. 1. 2. 3. 4. 5
arr [5, 7, 13, 7, 4, 8]
^i ^j ^基準點
5比8小，i要加一，繼續比較，j也加一：
index 0. 1. 2. 3. 4. 5
arr [5, 7, 13, 7, 4, 8]
^j ^基準點
^i
7比8小，i要加一，繼續比較，j也加一：
index 0. 1. 2. 3. 4. 5
arr [5, 7, 13, 7, 4, 8]
^j ^基準點
^i
13比8大，也就是說該值不能留在基準點左邊，該換位子。i為有多少元素可以留在基準點左邊，也就是說i的下一個就不能在基準點左邊了。那麼，把基準點跟第i+1個元素交換。i+1成為新的基準點。
index 0. 1. 2. 3. 4. 5
arr [5, 7, 13, 7, 4, 8]
^j ^基準點
^i
index 0. 1. 2. 3. 4. 5
arr [5, 7, 8, 7, 4, 13]
^新基準點
^i
新基準點將原本的陣列劃分出「左陣列」跟「右陣列」，左陣列只是比舊基準點還要小，但不代表排序過。把「左陣列」跟「右陣列」也做一樣的步驟：
右陣列 右陣列
[5, 7] 8 [7, 4, 13]
^新基準點（視為已經排序好）
左陣列 新基準點 右陣列
[5, 7] 8 [7, 4, 13]
^左陣列的基準點 ^右陣列的基準點
let arr = [15, 3, 17, -17, 3.1415, 18, 20, 2, 1, 666];
quickSort(0, arr.length - 1);
console.log(arr);
// partition 會回傳一個基準點index
function partition(p, r) {
let x = arr[r]; // pivot
let i = p - 1; // i代表基準點之前有幾個元素
for (let j = p; j <= r - 1; j++) {
if (arr[j] <= x) {
i += 1;
// 交換 arr[i] 跟 arr[j]
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交換 arr[i+1] 跟 arr[r]
let temp = arr[i + 1];
arr[i + 1] = arr[r];
arr[r] = temp;
return i + 1; // 求出新基準點
}
function quickSort(p, r) {
if (p < r) {
let q = partition(p, r); // 劃分 求出基準點 一開始把最後一個index當成基準點
quickSort(p, q - 1); // 基準點之前 劃分出左半部 繼續劃分
quickSort(q + 1, r); // 基準點之後 劃分出右半部 繼續劃分
}
}
-
最差： 從partition這個函式的迴圈來看，知道迴圈會跑的次數等於r-p，最糟就是跑整個長度為n的陣列，quickSort內分別還會再去跑兩次quickSort（內有一次partition），這兩次partition的迴圈最多還會跑的次數等於r-p。最糟的情況下，時間複雜度為O(n^2)。
-
最佳與平均： partition會根據基準點一直把陣列切成兩部分，再持續切成兩部分，直到無法再切下去。1個陣列切成2段，2個陣列切成4段，4個陣列切成8段。假設長度為8的陣列，基準點又剛好很完美的把陣列切成兩半，先切一次，變成4+4，再切第二次，變成2+2+2+2，再切第三次1+1+1+1+1+1+1+1；可以得知： 長度n的陣列，可以切log2 n次。時間複雜度為O(logn)。 而切出來的每個陣列跑n次迴圈，時間複雜度O(n)， 組起來複雜度剛好是O(nlogn)。
- 最差：O(n^2)
- 最佳：O(nlogn)
- 平均：O(nlogn)