排序算法
快速排序（O(nlogn))
思想：分治
做法：
- 确定分界点：
nums[l]或nums[r]或nums[(l + r) / 2]或随机
- 调整范围，使得分界点左边的数小于分界点的数值，分界点右边的数大于分界点的数值
- 递归处理左右两段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void quickSort(vector<int>& nums, int l, int r) {
if (l >= r)
return;
int x = nums[(l + r) >> 1];
int i = l, j = r;
while (i <= j) {
while (nums[i] < x)
++i;
while (nums[j] > x)
--j;
if (i >= j)
break;
swap(nums[i++], nums[j--]);
}
quickSort(nums, l, j);
quickSort(nums, j + 1, r);
}
|
归并排序(O(nlogn))
思想：分治
做法：
- 确定分界点：
mid = (l + r) / 2
- 递归排序左右两端
- 归并：将左右两段合二为一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void mergeSort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
// 使用数组，速度快非常多，大概是使用vector的两倍
int n = r - l + 1;
int temp[n];
int i = l, j = mid + 1, idx = 0;
while (i <= mid && j <= r) {
temp[idx++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
}
while (i <= mid) temp[idx++] = nums[i++];
while (j <= r) temp[idx++] = nums[j++];
for (int i = 0; i < n; ++i) {
nums[l + i] = temp[i];
}
}
|
堆排序(O(nlogn))
思想：利用小根堆完成排序
做法：
- 将数组里的所有数扔到堆里
- 将堆按序输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void HeapSort(vector<int>& nums) {
priority_queue<int, vector<int>, greater<int>> q(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); ++i) {
nums[i] = q.top();
q.pop();
}
}
int main() {
vector<int> nums({3, 5, 2, 5, 7, 4, 9, 0});
HeapSort(nums);
for (int i : nums)
cout << i << " ";
cout << endl;
return 0;
}
|
计数排序(O(n + k))
思想：遍历
做法：
- 确定范围
- 去数每个数的数量
- 重构数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void countSort(vector<int>& nums) {
int maxVal = -1;
for (int num : nums) {
maxVal = max(maxVal, num);
}
vector<int> count(maxVal + 1);
for (int num : nums) {
++count[num];
}
int index = 0; //原数组修改坐标
for (int val = 0; val < count.size(); ++val) {
while (count[val] > 0) {
--count[val];
nums[index++] = val;
}
}
}
int main() {
vector<int> test = {4, 5, 2, 1, 4, 2, 3, 4, 4, 0, 8};
for (auto a : test) {
cout << a << ' ';
}
cout << endl;
countSort(test);
for (auto a : test) {
cout << a << ' ';
}
cout << endl;
}
|
冒泡排序(O(n^2))
思想：两遍遍历
做法：
- 第一层遍历决定开始的位置
- 每二层遍历将最大值放到数组的最右边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <iostream>
#include <vector>
using namespace std;
void BubbleSort(vector<int>& nums) {
int n = nums.size();
if (n <= 1)
return;
for (int i = 1; i < n; ++i) {
bool check = false;
for (int j = 1; j < n - i + 1; ++j) {
if (nums[j] < nums[j - 1]) {
std::swap(nums[j], nums[j - 1]);
check = true;
}
}
if (!check)
break;
}
}
int main() {
vector<int> nums({3, 5, 2, 5, 7, 4, 9, 0});
BubbleSort(nums);
for (int i : nums)
cout << i << " ";
cout << endl;
return 0;
}
|
插入排序
思想：将数组分为已排序和未排序两部分，每次将未排序中的第一个数插入到已排序的部分中，未排序的数量为0时排序完成
做法：
- 数组的首数字为已排序部分，其余部分为未排序部分
- 两层遍历，将未排序的第一个数字与已排序的部分逐个比较直到插入到合适的位置中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
#include <vector>
using namespace std;
void InsertSort(vector<int>& nums) {
int n = nums.size();
if (n <= 1)
return;
for (int i = 1; i < n; ++i) {
for (int j = i; j > 0 && nums[j] < nums[j - 1]; --j) {
swap(nums[j], nums[j - 1]);
}
}
}
int main() {
vector<int> nums({3, 5, 2, 5, 7, 4, 9, 0});
InsertSort(nums);
for (int i : nums)
cout << i << " ";
cout << endl;
return 0;
}
|
选择排序
思想：将将数组分为已排序和未排序两部分，每次将未排序中的最小的元素放到已排序部分的末尾
做法：
- 已排序部分为无，整个数组都是未排序部分
- 两层遍历，每次选择一个最小的值放到已排序的末尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <iostream>
#include <vector>
using namespace std;
void SelectSort(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return;
for (int i = 0; i < n; ++i) {
int idx = i;
for (int j = i; j < n; ++j) {
if (nums[j] < nums[idx]) {
idx = j;
}
}
swap(nums[i], nums[idx]);
}
}
int main() {
vector<int> nums({3, 5, 2, 5, 7, 4, 9, 0});
SelectSort(nums);
for (int i : nums)
cout << i << " ";
cout << endl;
return 0;
}
|
Sugar