x-note
Search…
快速排序
快速排序(Quick Sort)又称为划分交换排序(partition-exchange sort)是一种有效率的排序算法。
  • 平均时间复杂度:
    O(nlog2n)O({n}\log_{2}{n})
  • 最好时间复杂度:
    O(nlog2n)O({n}\log_{2}{n})
  • 最坏时间复杂度:
    O(n2)O(n^2)
  • 空间复杂度:根据实现方式不同为
    O(n)O(n)
    O(log2n)O(\log_{2}{n})
  • 稳定性:不稳定
  • 排序方式:原地(In-place)
步骤:
  1. 1.
    从序列中挑出一个元素作为基准(Pivot),一般选取序列中的第一个;
  2. 2.
    从后向前遍历剩余元素,找到第一个比基准小的元素的索引;
  3. 3.
    从前向后遍历剩余元素,找到第一个比基准数大的元素的索引;
  4. 4.
    交换两个元素;
  5. 5.
    重复 2~4,直到从后向前的游标和从前向后的游标重叠;
  6. 6.
    交换基准与当前两个游标重叠的位置的元素,此时,所有比基准值小的元素放在基准前面,所有比基准大的放在基准后面(相同的可放在前面或后面);
  7. 7.
    划分结束后,以基准所在位置划分左右两个分区;
  8. 8.
    对新划分的分区执行 1~5,直到无法划分分区。
可以简单理解为,从每个的分区中,取一个基准值,然后找到这个基准值所在的位置。
递归实现:
1
function swap(arr, i, j) {
2
let tmp = arr[i];
3
arr[i] = arr[j];
4
arr[j] = tmp;
5
}
6
7
function quickSort(arr, left, right) {
8
const len = arr.length;
9
if (left > right) {
10
return arr;
11
}
12
let pivot = arr[left];
13
let i = left;
14
let j = right;
15
while (i != j) {
16
while (arr[j] >= pivot && i < j) {
17
j--;
18
}
19
while (arr[i] <= pivot && i < j) {
20
i++;
21
}
22
if (i < j && arr[i] !== arr[j]) {
23
swap(arr, i, j);
24
}
25
}
26
27
if (left !== i && arr[left] !== arr[i]) {
28
swap(arr, left, i);
29
}
30
31
quickSort(arr, left, i - 1);
32
quickSort(arr, i + 1, right);
33
34
return arr;
35
}
36
37
let arr = [3, 7, 8, 5, 2, 1, 9, 5, 4];
38
quickSort(arr, 0, arr.length - 1); // [1, 2, 3, 4, 5, 5, 7, 8, 9]
Copied!
非递归实现:
1
function swap(arr, i, j) {
2
let tmp = arr[i];
3
arr[i] = arr[j];
4
arr[j] = tmp;
5
}
6
const quickSort = (arr) => {
7
const stack = [0, arr.length - 1];
8
9
while (stack.length > 0) {
10
const left = stack.pop();
11
const right = stack.pop();
12
13
if (left >= right) {
14
continue;
15
}
16
17
let i = left;
18
let j = right;
19
let p = arr[left];
20
while (i < j) {
21
while (i < j && arr[j] >= p) {
22
j--;
23
}
24
while (i < j && arr[i] <= p) {
25
i++;
26
}
27
if (i !== j && arr[i] !== arr[j]) {
28
swap(arr, i, j);
29
}
30
}
31
stack.push(left, i - 1);
32
stack.push(i + 1, right);
33
}
34
return arr;
35
};
36
37
let arr = [3, 7, 8, 5, 2, 1, 9, 5, 4];
38
quickSort(arr, 0, arr.length - 1); // [1, 2, 3, 4, 5, 5, 7, 8, 9]
Copied!
Copy link