各种排序
快速排序、归并排序、桶排序、堆排序
1、快速排序（quick_sort）
时间复杂度：\(O(nlogn)\)
// 快速排序模版
void quick_sort(int q[], int l, int r) // 数组 ， 左端点， 右端点
{
if (l >= r) return;
// “ >> ” : 右移运算符，相当于 除以2
int x = q[l + r >> 1], i = l - 1, j = r + 1;
while (i < j)
{
while (q[++i] < x);
while (q[--j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j); // 排序左侧
quick_sort(q, j + 1, r);// 排序右侧
}
2、归并排序（merge_sort）
时间复杂度：\(O(nlogn)\)
// 注意：归并排序需要一个辅助数组 tem
void merge_sort(int q[], int l, int r)
{
if (l >= r)
return;
int mid = l + r >> 1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r); // 先分，回来时就排好序了
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (q[i] <= q[j])
tem[k++] = q[i++];
else
tem[k++] = q[j++];
}
while (i <= mid) tem[k++] = q[i++];
while (j <= r) tem[k++] = q[j++];
for (int i = l, j = 0; i <= r; i++, j++)
q[i] = tem[j];
}
题目链接：
车厢重组 - 洛谷
3、桶排序（bucket_sort）
时间复杂度：\(O(n)\) 注意：如果数据的值域超过了1e8就内存会溢出了
const int MAX_NUM = 1e8;
int sum[MAX_NUM]; // 值域
void bucket_sort(int q[])
{
for (int i = 0; i < n; i++)
sum[q[i]]++;
for (int i = 0, j = 0; j < n; i++)
{
while (sum[i]--)
q[j++] = i;
}
}
4、堆排序
时间复杂度：\(O(nlogn)\)
注：底层基于 完全二叉树 实现，分为 大根堆、小根堆
堆排序是在输入数据的时候就排好序了！！！
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N], sz;
int n, m;
// down
void down(int u)
{
int t = u;
if(u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(t != u)
{
swap(h[t],h[u]);
down(t);
}
}
int main()
{
cin >> n >> m; // m 是要输出排序后的数组的前多少个
for(int i = 1; i <= n; i++) cin >> h[i];
sz = n;
// 建堆(排好序了)
for(int i = n / 2; i; i--) down(i);
// 为什么从 n / 2 开始，因为 n/2所在的点是 最后一个有孩子的节点。
while(m --)
{
cout << h[1] << " ";
h[1] = h[sz--];
down(1);
}
return 0;
}
5、库函数sort，在头文件 algorithm 中
时间复杂度：\(O(nlogn)\) 函数原型 ： sort(start, end, cmp);
#include<algorithm>
注意： cmp是比较器，是可选参数，可以自己用来定义比较类型（当然也有官方提供的）
bool cmp(...){...}
// 比如要对数组a自定义排序 , 传数组的地址（起始地址，终止地址，比较器）
sort(a, a + n, cmp);
// 或者是vector容器排序， 传容器的迭代器（起始迭代器，终止迭代器，比较器）
sort(a.begin(), a.end(), cmp)
// 如果不加cmp，默认只能给 基础类型 按 升序排列
sort(a, a + n);
// 官方提供的比较器 greater<int>() => 从大到小排序
sort(a, a + n, greater<int>()); // greater<int>()谓词, 二元谓词，后面讲
// cmp比较函数中的参数：
// 1、基本数据类型
bool cmp(int a, int b)
{
return a > b; // 作用就是从大到小排列
}
// 2、结构体类型
// 2.1 比如按照学生的成绩降序排序
struct Student
{
string name;
int score;
};
// 加 引用符号 的作用：防止传递参数的时候再复制一份占用内存
bool cmp(Student &s1, Student &s2)
{
return s1.score > s2.score;
}
// 2.2 多条件排序，再加个学号，如果学生成绩相同的话，学号靠前的先输出
struct Student
{
int id;
string name;
int score;
};
bool cmp(Student &s1, Student &s2)
{
if(s1.score != s2.score) // 先判断不同，再判断相同
return s1.score > s2.score; // 大于：降序排列
return s1.id < s2.id; // 小于 ： 升序排列
}
// 返回值的理解：
1. 比如待排序的序列为 ：4 5 3 1 2 降序排列
第一次调用cmp ： 传递的参数，a: 5, b: 4 !注意：是先交换再传值进来
// 如果满足关系 就这样
2. 序列变为 ： 5 4 3 1 2
第二次调用cmp ： 传递的参数， a：3, b: 4
// 不满足，换回来
3. 序列保持原样： 5 4 3 1 2
第三次调用 ： a: 2, b: 1
// 满足， 就这样了
4. 序列变为 ： 5 4 3 2 1
调用结束，排好序了。
参考博客：C++ Sort函数详解
6、STL模版（priority_queue）
priority_queue<int>: 优先队列，可以叫做堆， 默认为 大根堆
要实现小根堆的话 ： priority_queue<int, vector<int>, greater<int>> heap;
// 1、引入头文件
#include <queue>
// 2.1、定义一个堆（优先队列）
priority_queue<int> heap; // 默认大根堆的存储int类型的优先队列
// 2.2、定义一个小根堆
priority_queue<int, vector<int>, greater<int>> heap; // 小根堆的定义
// 3、堆方法
heap.push(1); // 插入
heap.top(); // 取最大（最小）值
heap.pop(); // 删除最大（最小）值
heap.empty(); // 判断是否为空
heap.size(); // 获取队列长度
参考博客：C++ 优先队列 priority_queue 使用篇_爱喝酸奶！的博客-CSDN博客
重载运算符排序
重载operator
operator ：是c++的关键字，用于重新定义运算符的含义
比较常见重载的运算符：'<' '>' '+' '-' '*' '()'
// 比如对结构体排序
struct Student
{
int id;
string name;
int score;
bool operator < (const Student &s) const
{
if(s.score != score)
return score > s.score
return id < s.id;
}
}
sort(a, a + n) // 这样就重载了sort函数的默认排序规则（'<'），它知道怎么排序了
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
struct Student
{
int id;
string name;
int score;
bool operator<(const Student &s) const
{
if (s.score != score)
return score > s.score;
return id < s.id;
}
} s[N];
int n;
bool cmp(Student &s1, Student &s2)
{
if (s1.score != s2.score)
return s1.score > s2.score;
return s1.id < s2.id;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s[i].name >> s[i].score;
s[i].id = i + 1;
}
sort(s, s + n);
// sort(s, s + n, cmp);
for (int i = 0; i < n; i++)
{
cout << s[i].id << " " << s[i].name << " " << s[i].score << endl;
}
return 0;
}
参考博客：C++ operator重载运算符详解_Janus_V的博客-CSDN博客
谓词(使用谓词，要先了解C++的class类)
一元谓词和二元谓词
谓词：返回值为bool类型的 仿函数（类似函数，不是函数，因为重载了小括号）
一元谓词，每个元素和一个条件比较
二元谓词，两个元素相比较，常用于排序
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class GreaterFive
{
public:
bool operator()(int v) // 一元谓词，只有一个参数
{
return v > 5;
}
};
class Mycmp
{
public:
bool operator()(int x, int y) // 二元谓词，有两个参数
{
return x > y;
}
};
int n;
vector<int> v;
void print()
{
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test1()
{
// 查找大于5的数字
vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
if (it != v.end())
cout << "Yes: " << *it << endl;
else
cout << "No find" << endl;
}
void test2()
{
print();
sort(v.begin(), v.end(), Mycmp()); // 降序
print();
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
v.push_back(i);
}
test1();
// test2();
return 0;
}
小tips：使用auto关键字自动推导类型(在C++11之后的版本才可以使用)
// 比如有函数的返回值是个迭代器
vector<int>::iterator it = v.begin();
// 我们可以简写前面一长串为：auto
auto it = v.begin();
// 简化代码量
// 还可以在范围for循环中使用，自动推导类型
for(auto u : v)
{
}