20220710 更新
快速排序
快排算法为一种递归排序算法, 每次随机取数组里面的一个数为基准, 通过O(n)次交换, 把小于基准的数放到基准的左边, 大于基准的数字放到基准的右边, 然后在递归地对两边进行快排.
直接上代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void quickSort(vector<int> &data, int a, int b) {
if (b - a <= 1) return;
int base = data[a];
int left = a, right = b - 1;
while (right > left) {
while (right > left && data[right] >= base) right--;
if (right > left) data[left++] = data[right];
while (right > left && data[left] <= base) left++;
if (right > left) data[right--] = data[left];
}
data[left] = base;
quickSort(data, a, left);
quickSort(data, left + 1, b);
}
|
这里以模拟过程来讲解
原始数据为
这里取出来的数用X表示, 但并不是真的取出来被X覆盖, 只是被复制到别的地方去了,
可以随意被其他数覆盖, 原来位置的值还是没变的, 只是没有了意义, 于是用X代替表示
基准取第一位base = 3, left = 0, right==4
1
2
3
| X 5 4 6 2
|
---> base
|
从最右边开始搜索小于base的数, 找到了2<3, data[left++] = data[right]
1
2
3
| 2 5 4 6 X
^ |
|_______|
|
此时left == 1, 从左边开始搜索, 寻找>base的数字,
找到了5, 执行 data[right--] = data[left]
1
2
3
| 2 X 4 6 5
| ^
|_____|
|
继续从right搜索, 此时right == 3, 向左搜索小于base的数字, 一直找到right==left==1都没找到,
便停止搜索, 并把base填回到搜索结束的位置上
1
2
3
4
| 2 3 4 6 5
^
|
---- base
|
此时base(3)的位置把数组分成了小于base的一段[0, 1)和大于base的部分[2, 5)
继续递归地执行
1
2
| quickSort(data, 0, 1)
quickSort(data, 2, 5)
|
即可完成排序
时间复杂度平均O(logn) 最坏 O(n^2), 空间O(1)
归并排序
归并排序分为两个过程, 先不停二分, 再逐步合并, 由于要合并, 因此空间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| vector<int> mergeSort(vector<int> &data, int a, int b) {
vector<int> ans;
if (b - a == 1) return vector<int>{data[a]};
// 切分
int mid = a + (b - a) / 2;
auto part1 = mergeSort(data, a, mid);
auto part2 = mergeSort(data, mid, b);
// 合并
int p1 = 0, p2 = 0;
while (p1 < part1.size() && p2 < part2.size()) {
if (part1[p1] <= part2[p2]) ans.push_back(part1[p1++]);
else ans.push_back(part2[p2++]);
}
while (p1 < part1.size()) ans.push_back(part1[p1++]);
while (p2 < part2.size()) ans.push_back(part2[p2++]);
return ans;
}
|
可以看到先是不停的找到中间点切分, 然后递归地mergeSort
1
2
3
| int mid = a + (b - a) / 2;
auto part1 = mergeSort(data, a, mid);
auto part2 = mergeSort(data, mid, b);
|
然后将排好序的part1, part2合并, 这里的合并就是简单的合并有序数组
1
2
3
4
5
6
7
| int p1 = 0, p2 = 0;
while (p1 < part1.size() && p2 < part2.size()) {
if (part1[p1] <= part2[p2]) ans.push_back(part1[p1++]);
else ans.push_back(part2[p2++]);
}
while (p1 < part1.size()) ans.push_back(part1[p1++]);
while (p2 < part2.size()) ans.push_back(part2[p2++]);
|
加了一个小优化的版本, 在数组长度为2时, 直接手动排序, 不必继续递归下去了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| vector<int> mergeSort(vector<int> &data, int a, int b) {
vector<int> ans;
if (b - a == 1) return vector<int>{data[a]};
// 优化: 只有两个元素的时候直接排序并返回
if (b - a == 2) {
return data[a] <= data[a + 1] ? vector<int>{data[a], data[a + 1]}
: vector<int>{data[a + 1], data[a]};
}
// 切分
int mid = a + (b - a) / 2;
auto part1 = mergeSort(data, a, mid);
auto part2 = mergeSort(data, mid, b);
// 合并
int p1 = 0, p2 = 0;
while (p1 < part1.size() && p2 < part2.size()) {
if (part1[p1] <= part2[p2]) ans.push_back(part1[p1++]);
else ans.push_back(part2[p2++]);
}
while (p1 < part1.size()) ans.push_back(part1[p1++]);
while (p2 < part2.size()) ans.push_back(part2[p2++]);
return ans;
}
|