常见排序算法概述表
| 排序算法 |
时间复杂度（平均） |
时间复杂度（最坏） |
空间复杂度 |
是否稳定 |
适用场景/特点 |
| 冒泡排序 |
|
|
|
是 |
简单，适合小数据量 |
| 选择排序 |
|
|
|
否 |
简单，交换次数少 |
| 插入排序 |
|
|
|
是 |
适合部分有序、小数据量 |
| 希尔排序 |
|
|
|
否 |
改进插入排序，较快 |
| 快速排序 |
|
|
|
否 |
实际应用最广泛 |
| 归并排序 |
|
|
|
是 |
稳定，适合大数据 |
| 堆排序 |
|
|
|
否 |
不稳定，适合大数据 |
| 计数排序 |
|
|
|
是 |
适合整数、范围小 |
| 桶排序 |
|
|
|
是 |
适合均匀分布数据 |
| 基数排序 |
|
|
|
是 |
适合数字、字符串排序 |
C++
最大堆
1
2
3
4
5
| priority_queue<
T, // 存储的数据类型
vector<T>, // 底层容器类型（一般用 vector）
Compare // 比较函数（默认是 less<T>，即大顶堆）
> pq;
|
1
2
3
4
5
| priority_queue<
T, // 存储的数据类型
vector<T>, // 底层容器类型（一般用 vector）
Compare // 比较函数（默认是 less<T>，即大顶堆）
> pq;
|
1
2
3
4
5
| priority_queue<pair<int, int>> pq;
pq.push({3, 100});
pq.push({1, 200});
pq.push({2, 50});
cout << pq.top().first;
|
最小堆
1
| priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
|
pair
访问方式：i.second, i.first，如果用不是 get<0>则会耗时
滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
最大堆
维护一个最大堆，（值，下标）。遍历数组进堆，然后弹出不符合滑动窗口的元素，堆顶即为当前窗口最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
priority_queue<pair<int,int>> pg;
vector<int> result;
for(int i=0;i<nums.size();i++){
pg.emplace(nums[i],i);
if(i>=k-1){
while(pg.top().second<=i-k){
pg.pop();
}
result.push_back(pg.top().first);
}
}
return result;
}
};
|
单调队列
维护一个单调递减队列，遍历数组进队列，然后弹出不符合滑动窗口的元素，队首即为当前窗口最大值。若队列中当前最小值小于新加入值，则将其弹出，直到队列为空或队尾值大于新加入值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dp;
vector<int> result;
for(int i=0;i<nums.size();i++){
while(!dp.empty()&&nums[dp.back()]<=nums[i]){
dp.pop_back();
}
dp.push_back(i);
if(dp.front()<=i-k){
dp.pop_front();
}
if(i>=k-1) result.push_back(nums[dp.front()]);
}
return result;
}
};
|
注意stack 或 queue只有push
deque有push_front push_back pop_front pop_back
指针和引用
Node* a
“a 是一个指向 Node 的指针”
a 存放的是 Node 的地址
Node& a
“a 是一个 Node 的引用”
a 是某个 Node 的别名
哈希表
构造
#include
注意value不一定是int
std::unordered_map<key_type, value_type> map_name;
哈希表遍历
c++17
1
2
3
| for (auto& [key, vec] : map) {
result.push_back(vec);
}
|
常见用法补充
插入/修改
1
2
| map[key] = value;
map.insert({key, value});
|
查找
1
2
3
4
5
6
| if (map.count(key)) { }
if (map.find(key) != map.end()) { }
auto it = map.find(key);
if (it != map.end()) {
}
|
删除
计数器用法
1
2
| unordered_map<int, int> cnt;
cnt[x]++;
|
判断键是否存在
遍历所有键值对
1
2
3
| for (const auto& [k, v] : map) {
std::cout << k << ": " << v << std::endl;
}
|
其他常用操作
1
2
| map.clear();
map.size();
|
1
2
3
| for (auto& p : map) {
result.push_back(p.second);
}
|
常见用法补充
插入/修改
1
2
3
| map[key] = value;
map.insert({key, value});
map.try_emplace(key, value);
|
查找
1
2
3
4
5
6
| if (map.count(key)) { }
if (map.find(key) != map.end()) { }
auto it = map.find(key);
if (it != map.end()) {
}
|
删除
计数器用法
1
2
| unordered_map<int, int> cnt;
cnt[x]++;
|
判断键是否存在
遍历所有键值对
1
2
3
| for (const auto& [k, v] : map) {
std::cout << k << ": " << v << std::endl;
}
|
其他常用操作
1
2
| map.clear();
map.size();
|
stl
end()
C++ STL 里，end() 的定义是：
“指向容器最后一个元素之后的那个位置”，
它不是有效元素，不能解引用。
lambda
1
2
3
| [](const string& a, const string& b) {
return a + b > b + a;
}
|
nth_element快速求第k大值
左小右大
1
2
3
4
5
6
7
8
|
nth_element(v.begin(), v.begin() + v.size()/2, v.end());
int median = v[v.size()/2];
auto midptr = nums.begin() + n / 2;
nth_element(nums.begin(), midptr, nums.end());
int mid = *midptr;
|
lambda
注意lambda“}”后还有；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int x = 10;
auto f1 = [] { std::cout << "我啥也不返回\n"; };
f1();
auto f2 = [] { return 42; };
int n = f2();
auto f3 = [] {
std::cout << "干活\n";
return 100;
};
auto f3 = []() -> int {
std::cout << "干活\n";
return 100;
};
int result = f3();
|
二进制相关
除2
1
2
| int mid = (l + r) >> 1;
int half = n >> 1;
|
