文章目录
一、二分搜索算法
1. 非递归代码
// 找到返回索引，找不到返回-1
int binary_search(const vector<int>& vec, int val) {
int left = 0;
int right = vec.size() - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (vec[mid] == val) {
return mid;
}
else if (vec[mid] < val) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
2. 递归代码
递归函数特点：
- 不管什么数据规模，求解问题的方式是一样的
- 有递推公式
写递归函数注意点：
- 搞清楚递归函数的意义，返回值、参数列表以及完成什么功能
- 递要有结束的条件
- 每个数据规模要写好计算关系，即递推公式
递归问题的思考是水平方向上的，递归问题的执行是竖直方向上的
// 函数功能：在[left, right]区间内搜索val，找到返回下标，找不到返回-1
int recur_binary_search(const vector<int>& vec, int left, int right, int val) {
// 递归结束条件
if (left > right) {
return -1;
}
int mid = (left + right) >> 1;
if (vec[mid] == val) {
return mid; // 找到返回索引
}
else if (vec[mid] > val) {
return recur_binary_search(vec, left, mid - 1, val); //在[left, mid - 1]区间内搜索val，找到返回下标，找不到返回-1
}
else {
return recur_binary_search(vec, mid + 1, right, val); //在[mid + 1, right]区间内搜索val，找到返回下标，找不到返回-1
}
}
二、冒泡排序算法
void bubble_sort(vector<int>& vec) {
// 外层控制趟数，n个元素最多n-1趟，最后一趟只有一个元素所以可以减1
for (int i = 0; i < vec.size() - 1; i++) {
// 假设这一趟排序没有交换元素
bool is_swap = false;
// 每趟会处理一个元素，所以减i。减1是因为用vec[j]和vec[j+1]比较
for (int j = 0; j < vec.size() - 1 - i; j++) {
if (vec[j] > vec[j + 1]) {
int tmp = vec[j];
vec[j] = vec[j + 1];
vec[j + 1] = tmp;
is_swap = true;
}
}
// 一趟排序结束，判断是否进行了元素交换
if (!is_swap) {
break;
}
}
}
冒泡排序的效率较低，原因在于交换元素的次数过多，但是可以提前终止
三、选择排序
void choice_sort(vector<int>& vec) {
if (vec.size() < 2) {
return;
}
// 外循环用于控制趟数
for (int i = 0; i < vec.size() - 1; i++) {
int min_val = vec[i]; // 用于记录当前最小值
int min_i = i; // 记录最小值的位置
// 找到无序序列中最小的元素，并记录准备交换
for (int j = i+1; j < vec.size(); j++) {
if (vec[j] < min_val) {
min_val = vec[j];
min_i = j;
}
}
if (min_i != i) {
int tmp = vec[i];
vec[i] = vec[min_i];
vec[min_i] = tmp;
}
}
}
选择排序的效率比冒泡排序的效率稍微高一点，原因在于没有很多的赋值操作（每一趟只交换赋值一次），但是有很多的比较操作，而且也不像冒泡排序一样可以提前终止。
不稳定： 比如有序列5、5、3，第一个5和3交换，就成了3、5、5
四、插入排序
如果数据趋于有序，插入排序是所有排序算法中，效率最高的排序算法。不仅仅没有交换，比较次数也较少
算法思想：前面的序列是有序的，把无序序列中第一个元素按顺序插入到有序序列，一边找一边移动元素，找第一个 小于等于（可保证稳定性） 自己的元素，查到该元素后面
void insert_sort(vector<int>& vec) {
if (vec.size() < 2) {
return;
}
for (int i = 1; i < vec.size(); i++) {
int val = vec[i];
int j;
// 在有序序列中查找第一个小于等于当前元素的元素
for (j = i - 1; j >= 0; j--) {
// 注意这个地方是<=val，不是<=vec[i]，vec[i]可能早就被覆盖了
if (vec[j] <= val) {
break;
}
else {
vec[j + 1] = vec[j];
}
}
vec[j + 1] = val;
}
}
五、希尔排序
如果数据趋于有序，插入排序是所有排序算法中，效率最高的排序算法。而 希尔排序是从全局的角度把数据调整得趋于有序 ，利用插入排序的这一特点，最后进行一次插入排序（gap=1）
void shell_sort(vector<int>& vec) {
if (vec.size() < 2) {
return;
}
for (int gap = vec.size() >> 1; gap > 0; gap >>= 1) {
for (int i = gap; i < vec.size(); i++) {
int val = vec[i];
int j;
// 在有序序列中查找第一个小于等于当前元素的元素
for (j = i - gap; j >= 0; j -= gap) {
// 注意这个地方是<=val，不是<=vec[i]，vec[i]可能早就被覆盖了
if (vec[j] <= val) {
break;
}
else {
vec[j + gap] = vec[j];
}
}
vec[j + gap] = val;
}
}
}
六、快速排序
可以看出，如果这棵二叉树比较平衡，那么深入的层数会更少，也就是数据分布比较均匀，比较乱序的时候，二叉树会比较平衡，快速排序的效率较高。若二叉树不平衡，则导致排序下效率低下
int partition(vector<int>& vec, int l, int r) {
int val = vec[l];
while (l < r) {
while (l < r && vec[r] > val) {
r--;
}
if (l < r) {
vec[l] = vec[r];
l++;
}
while (l < r && vec[l] < val) {
l++;
}
if (l < r) {
vec[r] = vec[l];
r--;
}
}
// 这里l == r，循环退出
vec[l] = val;
return l;
}
// 这是一个递归函数，主要功能是使得区间[begin, end]内的数据有序
void quick_sort(vector<int>& vec, int begin, int end) {
// 先写结束条件
// 这里是归，归的时候已经排序完成了
if (begin >= end) {
return;
}
// 这个操作是让[begin, end]区间内的第一个元素找到自己有序后的位置pos
// 先划分，找到基准元素的正确位置
int pos = partition(vec, begin, end);
// 再递
quick_sort(vec, begin, pos-1);
quick_sort(vec, pos+1, end);
}
平均时间复杂度：O(nlogn)
最坏时间复杂度：当数列本身有序的时候，除了叶子节点，所有节点都只有1个孩子节点，O(n^2)
空间复杂度：主要指的是递归的时候开辟的函数栈帧，O(logn)
最坏空间复杂度：同理，O(n)
快排算法优化
优化一：快排不断递归后，作用区间会越来越小，数据会越 趋于有序，这个时候使用插入排序 对该区间进行排序可以提升效率
void quick_sort(vector<int>& vec, int begin, int end) {
if (begin >= end) {
return;
}
// COUNT是数据规模
if(end - begin < COUNT / 10){
insert_sort(vec, begin, end);
return;
}
int pos = partition(vec, begin, end);
quick_sort(vec, begin, pos-1);
quick_sort(vec, pos+1, end);
}
优化二：三数取中法
void right_order(const vector<int>& vec, int& small, int& mid, int& big) {
int tmp;
if (vec[small] > vec[mid]) {
tmp = small;
small = mid;
mid = tmp;
}
if (vec[small] > vec[big]) {
tmp = small;
small = big;
big = tmp;
}
if (vec[mid] > vec[big]) {
tmp = mid;
mid = big;
big = tmp;
}
}
int partition(vector<int>& vec, int l, int r) {
int small = l;
int mid = (l + r) >> 1;
int big = r;
// 执行后，vec[small] < vec[mid] < vec[big]
right_order(vec, small, mid, big);
int val = vec[mid];
if (l != mid) {
int tmp = vec[l];
vec[l] = vec[mid];
vec[mid] = tmp;
}
while (l < r) {
while (l < r && vec[r] > val) {
r--;
}
if (l < r) {
vec[l] = vec[r];
l++;
}
while (l < r && vec[l] < val) {
l++;
}
if (l < r) {
vec[r] = vec[l];
r--;
}
}
// 这里l == r，循环退出
vec[l] = val;
return l;
}
// 这是一个递归函数，主要功能是使得区间[begin, end]内的数据有序
void quick_sort(vector<int>& vec, int begin, int end) {
// 先写结束条件
if (begin >= end) {
return;
}
// 这个操作是让[begin, end]区间内的第一个元素找到自己有序后的位置pos
// 先划分
int pos = partition(vec, begin, end);
quick_sort(vec, begin, pos-1);
quick_sort(vec, pos+1, end);
}
在递的过程中就进行分割，在归的过程中什么都不做
七、归并排序
// 将vec内[begin, mid]，[mid+1, end]进行有序合并
void merge(vector<int>& vec, int l, int mid, int r) {
int* tmp = new int[r - l + 1]();
int i = l; // 左子序列的索引
int j = mid + 1; // 右子序列的索引
int idx = 0; // 合并后序列的索引
while (i <= mid && j <= r) {
if (vec[i] <= vec[j]) {
tmp[idx++] = vec[i++];
}
else {
tmp[idx++] = vec[j++];
}
}
while (i <= mid) {
tmp[idx++] = vec[i++];
}
while (j <= r) {
tmp[idx++] = vec[j++];
}
for (i = l, j = 0; i <= r; i++, j++) {
vec[i] = tmp[j];
}
delete[] tmp;
}
// 使得vec区间[begin, end]内的元素变得有序
void merge_sort(vector<int>& vec, int begin, int end) {
if (begin >= end) {
return;
}
int mid = (begin + end) >> 1;
// 再分别对[begin, mid]， [mid+1, end]进行归并排序
// 这是递的过程，并没有进行排序
merge_sort(vec, begin, mid);
merge_sort(vec, mid+1, end);
// 归并的过程
merge(vec, begin, mid, end);
}
最好最坏时间复杂度：是一颗完美的平衡二叉树，树的深度都是O(logn)，每层为O(n)，O(nlogn)
空间复杂度：指的是递的时候开辟的函数栈帧O(logn)，以及合并的时候额外的空间O(n)，取大的O(n)
在递的过程中什么都不做，在归的过程中就进行合并排序
八、堆
1. 二叉堆的概念
最后一个非叶子节点计算公式：(n-1)/2
2. 调堆
入堆： 入堆只能从堆底入，然后进行调堆
出堆： 出堆只能从堆顶出，然后进行调堆
从堆顶出元素后，先将堆底元素放到堆顶，然后进行下沉：不断地将值大的孩子节点上调，自己下沉，直到没有孩子节点为止（即当前下标大于(n-1)/2）
调堆的时间复杂度都是树的高度：O(logn)
3. 用堆实现优先级队列
class PriorityQueue {
public:
// 定义函数对象类型
using Comp = function<bool(int, int)>;
PriorityQueue(int cap = 20, Comp comp = greater<int>())
:_size(0)
, _cap(cap)
, _comp(comp) {
_queue = new int[_cap];
}
PriorityQueue(Comp comp)
:_size(0)
, _cap(20)
, _comp(comp) {
_queue = new int[_cap];
}
~PriorityQueue(){
delete[] _queue;
}
public:
bool empty() const{
return _size == 0;
}
int top() const {
if (empty()) {
throw "queue is empty!";
}
return _queue[0];
}
int size() const {
return _size;
}
// push pop top size
void push(int val) {
if (_size == _cap) {
expand();
}
if (_size == 0) {
_queue[_size] = val;
}
else {
sift_up(_size, val); // 从堆底入堆
}
_size++;
}
void pop() {
if (empty()) {
throw "queue is empty!";
}
_size--;
// 堆中只有一个元素，出堆就不用管了
// 出堆后还有元素，需要继续调堆
if (_size > 0) {
sift_down(0, _queue[_size]); // 把最后一个节点放到0号位置，然后调整
}
}
private:
void expand() {
const int time = 2;
int* tmp = new int[_cap * time];
memcpy(tmp, _queue, _cap * sizeof(int)); // 逐字节拷贝，如果对于浅拷贝出错的对象，不可用memcpy
delete _queue;
_queue = tmp;
_cap *= time;
}
// 节点上浮操作：把正处于cur位置，值为val的节点上浮
void sift_up(int cur, int val) {
while (cur > 0) {
int father = (cur - 1) >> 1;
if (_comp(val , _queue[father])) {
_queue[cur] = _queue[father]; // 父节点被拉下来
cur = father; // 更新此时所处位置
}
else {
break;
}
}
_queue[cur] = val;
}
// 节点下沉，把正处于cur位置值为val的节点下沉
void sift_down(int cur, int val) {
// 当前节点cur不能超过最后一个内部节点
while (cur <= (_size - 1) / 2) {
int max_child = 2 * cur + 1; // 假定左孩子大
// 存在右孩子，且右孩子更大
if (2 * cur + 2 <= _size && _comp(_queue[2 * cur + 2], _queue[max_child])) {
max_child = 2 * cur + 2;
}
// 选出大孩子后，若大孩子大于当前val，则交换
if (_comp(_queue[max_child], val)) {
_queue[cur] = _queue[max_child];
cur = max_child;
}
else {
// 否则退出
break;
}
}
_queue[cur] = val;
}
private:
int* _queue;
int _size;
int _cap;
Comp _comp;
};
int main(){
const int COUNT = 10;
srand(time(nullptr));
PriorityQueue q([](int a, int b)->bool {return a < b; });
for (int i = 0; i < COUNT; i++) {
int val = rand() % 100;
q.push(val);
cout << val << " ";
}
cout << endl;
while (!q.empty()) {
cout << q.top() << " ";
q.pop();
}
cout << endl;
return 0;
}
写法1：
PriorityQueue q(less<int>()); // 写法在VS中不被当成构造对象，VS认为这是一个函数声明
cout<<typeid(q).name(); // class PriorityQueue __cdecl(struct std::less<int> (__cdecl*)(void))
PriorityQueue fun(int a);
cout << typeid(fun).name(); // class PriorityQueue __cdecl(int)
PriorityQueue q1(std::move(less<int>())); // 强行修改为右值，程序可以正常执行
用less类型显示生成临时对象当做实参传递，被处理成函数指针类型，VS认为这是一个函数声明，而不是构造一个对象，这属于编译器解析错误。
本应该是一个右值，这里没有被当成右值
注意： 最好不要显示构造临时对象，当作实参传递
写法2：
function<bool<int, int>> comp = less<int, int>();
PriorityQueue q(comp); // 不报错
写法3：
PriorityQueue q([](int a, int b){return a < b;}); // 不报错
4. 堆排序
从最后一个内部节点开始调堆，使得0号节点到第一个内部节点(n-1)/2全都满足堆性质，n表示最后一个节点的索引
堆顶元素和最后一个元素交换，则完成一个元素的排序任务
下一次排序，则少考虑一个元素
// 使索引为cur的节点满足堆性质，当前容器中需要排序的元素数量为size
void sift_down(vector<int>& vec, int cur, int size) {
int val = vec[cur];
int n = size - 1; // 最后一个节点的下标
while (cur <= (n - 1) >> 1) {
// 先找出大孩子
int max_child = 2 * cur + 1;
if (2 * cur + 2 <= n && vec[2 * cur + 2] > vec[max_child]) {
max_child = 2 * cur + 2;
}
if (vec[max_child] > val) {
vec[cur] = vec[max_child];
cur = max_child;
}
else {
// 已经满足堆性质，退出下沉过程
break;
}
}
vec[cur] = val;
}
void heap_sort(vector<int>& vec) {
// 首先进行堆化，从最后一个内部节点开始调堆
int n = vec.size() - 1; // 最后一个节点的下标
for (int i = (n - 1) >> 1; i >= 0; i--) {
sift_down(vec, i, vec.size()); // O(logn)
}
// 堆化以后，每次将堆顶元素和最后一个元素交换位置，并对堆顶元素sift_down，使堆顶元素满足堆性质
// i表示当前容器需要进行排序的元素个数
for (int i = vec.size(); i > 1; i--) {//O(logn)
// 和最后一个元素交换
int tmp = vec[0];
vec[0] = vec[i-1];
vec[i-1] = tmp;
sift_down(vec, 0, i-1); // 0表示每次只需要对堆顶元素sift_down
}
}
不稳定，只有两个相同元素能建立起比较关系的时候才有机会稳定。
在堆排序中，相同的值如果处于不同的子树，这两个值就无法比较，不稳定
总结：
数据量比较大，且均匀的时候，快排排序>归并排序>希尔排序>堆排序
- 归并排序比快排慢在，需要把合并的数据放在临时数组，最后拷贝到原数组
- 不管是快排还是归并排序，遍历数组的时候都是按顺序访问，这对CPU缓存是友好的（局部性原理），但是堆排序不是顺序访问，这不符合局部性原理，所以排序较慢
- 每次下沉调整的时候，需要把堆底的元素和堆顶元素交换，由于堆底元素是比较小的，所以下沉操作需要进行很多次，才能重新调成一个堆，这就耗费时间
九、STL中的sort源码解析
部分源码
template <class _RanIt, class _Pr>
_CONSTEXPR20 void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) { // order [_First, _Last)
_Adl_verify_range(_First, _Last);
const auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
_Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _Pass_fn(_Pred));
}
template <class _RanIt, class _Pr>
_CONSTEXPR20 void _Sort_unchecked(_RanIt _First, _RanIt _Last, _Iter_diff_t<_RanIt> _Ideal, _Pr _Pred) {
// order [_First, _Last)
for (;;) {
// 随着快排的进行，元素会趋于有序
// 快排过程中如果区间不大于 _ISORT_MAX = 32，转入插入排序
if (_Last - _First <= _ISORT_MAX) { // small
_Insertion_sort_unchecked(_First, _Last, _Pred);
return;
}
// _Ideal表示当前区间元素的个数
// 每次递归的时候，都会让_Ideal缩小
// 为了避免递归太深，当_Ideal <= 0的时候，停止递归，采用时间复杂度稳定为O(log2n)的堆排序
if (_Ideal <= 0) { // heap sort if too many divisions
_Make_heap_unchecked(_First, _Last, _Pred);
_Sort_heap_unchecked(_First, _Last, _Pred);
return;
}
// divide and conquer by quicksort
auto _Mid = _Partition_by_median_guess_unchecked(_First, _Last, _Pred);
_Ideal = (_Ideal >> 1) + (_Ideal >> 2); // allow 1.5 log2(N) divisions
if (_Mid.first - _First < _Last - _Mid.second) { // loop on second half
_Sort_unchecked(_First, _Mid.first, _Ideal, _Pred);
_First = _Mid.second;
} else { // loop on first half
_Sort_unchecked(_Mid.second, _Last, _Ideal, _Pred);
_Last = _Mid.first;
}
}
}
- 快速排序不是稳定的O(log2n)，最坏的情况会变成O(n^2)，可以通过 改插入排序 或者 三数取中 的方法改善情况恶化
- 参考STL中sort的源码，可设置变量
_Ideal控制递归深度 - 递归太深可能导致函数调用开销过多，甚至栈溢出，程序崩溃
- 若递归到已经快溢出了，还没排完，在sort中选择的是时间复杂度稳定的堆排序
冒泡会导致比较和交换次数过多，选择排序的比较次数也很多，在基本逆序的情况下，插入排序和快排的时间复杂度是O(n^2)，不了解数列特征的时候选择稳定的堆排序O(log2n)
考察空间复杂度，归并排序O(n)，此时肯定需要使用磁盘IO，效率很低。快速排序递归的空间复杂度为O(log2n)
外排序算法过程：
- 创建11个txt文件，分别写入1024M/11的数据，此时每个文件的数据不足100M
- 分别将11个文件的数据读入内存进行排序，然后写回硬盘，此时11个文件的数据都有序
- 从11个文件中分别读取1个数字，按照归并的思想选出最小的一个写入最终的文件，从写入数字对应的文件中再读取一个数，如此循环，直到所有数据排序完成
十、基数排序
void radix_sort(vector<int>& vec) {
if (vec.size() < 2) {
return;
}
vector<vector<int>> buckets(10);
// int max_num = *max_element(vec.begin(), vec.end());
int max_num = vec[0];
for (int i = 1; i < vec.size(); i++) {
if (vec[i] > max_num) {
max_num = vec[i];
}
}
int len = to_string(max_num).size();
int mod = 10; // 先取出取模后剩下的值
int dev = 1; // 再取出最高位
for (int i = 0; i < len; i++, mod *= 10, dev *= 10) {
for (int j = 0; j < vec.size(); j++) {
// 按照每个位放入对应的桶
int index = vec[j] % mod / dev;
buckets[index].push_back(vec[j]);
}
// 从每个桶中取出元素放回原始数组，并清空桶
int cur = 0;
for (int j = 0; j < 10; j++) {
for (int v : buckets[j]) {
vec[cur++] = v;
}
buckets[j].clear();
}
}
}
缺点：由于是按照数值进行索引，无法处理负数
void radix_sort(vector<int>& vec) {
if (vec.size() < 2) {
return;
}
// 生成20个桶，1-9号桶放负数，10-19号桶放正数
int bucket_num = 20;
vector<vector<int>> buckets(bucket_num);
int longest_num = abs(vec[0]);
for (int i = 1; i < vec.size(); i++) {
if (abs(vec[i]) > longest_num) {
longest_num = abs(vec[i]);
}
}
int len = to_string(longest_num).size();
int mod = 10; // 先取出取模后剩下的值
int dev = 1; // 再取出最高位
for (int i = 0; i < len; i++, mod *= 10, dev *= 10) {
for (int j = 0; j < vec.size(); j++) {
// 按照每个位放入对应的桶
int index = vec[j] % mod / dev + 10;
buckets[index].push_back(vec[j]);
}
// 从每个桶中取出元素放回原始数组，并清空桶
int cur = 0;
for (int j = 0; j < bucket_num; j++) {
for (int v : buckets[j]) {
vec[cur++] = v;
}
buckets[j].clear();
}
}
}
d表示数据的位数，空间复杂度主要是和桶相关