思想
快速排序:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据要小,再按这种方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,使整个数据变成有序序列。
实现步骤:
- 选择一个基准元素
target
(一般选择第一个数) - 将比
target
小的元素移动到数组左边,比target
大的元素移动到数组右边 - 分别对
target
左侧和右侧的元素进行快速排序
从上面的步骤中我们可以看出,快速排序也利用了分治的思想(将问题分解成一些小问题递归求解)
解法
写法1
单独开辟两个存储空间left
和right
来存储每次递归比target
小和大的序列
每次递归直接返回left、target、right
拼接后的数组
浪费大量存储空间,写法简单
function quickSort(array) {
if (array.length < 2) {
return array;
}
const target = array[0];
const left = [];
const right = [];
for (let i = 1; i < array.length; i++) {
if (array[i] < target) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return quickSort(left).concat([target], quickSort(right));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
写法2
记录一个索引l
从数组最左侧开始,记录一个索引r
从数组右侧开始
在l<r
的条件下,找到右侧小于target
的值array[r]
,并将其赋值到array[l]
在l<r
的条件下,找到左侧大于target
的值array[l]
,并将其赋值到array[r]
这样让l=r
时,左侧的值全部小于target
,右侧的值全部小于target
,将target
放到该位置
不需要额外存储空间,写法思路稍复杂(有能力推荐这种写法)
function quickSort(array, start, end) {
if (end - start < 2) {
return;
}
const target = array[start];
let l = start;
let r = end;
while (l < r) {
while (l < r && array[r] > target) {
r--;
}
array[l] = array[r];
while (l < r && array[l] < target) {
l++;
}
array[r] = array[l];
}
array[l] = target;
quickSort(array, start, l - 1);
quickSort(array, l + 1, end);
return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
复杂度
时间复杂度:平均O(nlogn)
,最坏O(n2)
,实际上大多数情况下小于O(nlogn)
空间复杂度:O(logn)
(递归调用消耗)
稳定性
不稳定