x-note
Search…
快速排序
快速排序（Quick Sort）又称为划分交换排序（partition-exchange sort）是一种有效率的排序算法。
- 平均时间复杂度：
- 最好时间复杂度：
- 最坏时间复杂度：
- 空间复杂度：根据实现方式不同为或
- 稳定性：不稳定
- 排序方式：原地（In-place）
步骤：
- 1.从序列中挑出一个元素作为基准（Pivot），一般选取序列中的第一个；
- 2.从后向前遍历剩余元素，找到第一个比基准小的元素的索引；
- 3.从前向后遍历剩余元素，找到第一个比基准数大的元素的索引；
- 4.交换两个元素；
- 5.重复 2~4，直到从后向前的游标和从前向后的游标重叠；
- 6.交换基准与当前两个游标重叠的位置的元素，此时，所有比基准值小的元素放在基准前面，所有比基准大的放在基准后面（相同的可放在前面或后面）；
- 7.划分结束后，以基准所在位置划分左右两个分区；
- 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!
Last modified 2yr ago
Copy link