# 【C++ 中级】 算法 题目记录
*C++ 技术栏*
本文章记录了有关 C++ 数据处理 题目 和 案例 的汇总。
## 目录
[TOC]
## 排序操作
### 冒泡排序
```
#include <vector>
#include "iostream"
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &v) {
auto it1 = v.begin(), it2 = v.end();
while (it1 != it2) {
cout << *it1++ << ' ';
}
return ostream1;
}
void swap(vector<int> &v, int index1, int index2) {
int t = v[index1];
v[index1] = v[index2];
v[index2] = t;
}
void sort(vector<int> &v) {
// 冒泡排序的操作其实就是双循环，内循环中用来将一个元素调整到合适的位置
// 且因为有 v.size() 个元素 所以我们要调整 v.size() 次 也就是 v.size() 轮
// 大概逻辑就是 第1次将第0索引的元素找到合适位置 第2次将第1索引的元素找到合适位置
for (int i1 = 0; i1 < v.size(); ++i1) {
cout << v << endl;
// 这里代表每一轮迭代 值得注意的是 冒泡排序每轮都是当前索引值和下一索引值比较
// 因此在这里我们循环限制条件里要减 1 避免出现越界
// 其次 因为迭代几轮，就代表后几个元素排序完毕，且 i1 代表轮数，因此这里我们为了快速，要减 i1（当然 可以不减）
for (int i = 0; i < v.size() - i1 - 1; ++i) {
// 在这里我们将当前索引的元素和下一个索引的元素进行比较，如果发现大/小就交换位置
// 这里也就是我们所说的排序的核心操作，在这里进行的位置交换！
if (v[i] > v[i + 1]) {
swap(v, i, i + 1);
}
}
}
}
int main() {
vector<int> v{10, 3, 4, 1, 60, 7};
sort(v);
cout << v << endl;
}
```
### 选择排序
这个就类似人类的排序操作，不断的寻找最值，然后追加到新容器或者旧容器中，下面就是一个示例。
```
#include <vector>
#include "iostream"
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &v) {
auto it1 = v.begin(), it2 = v.end();
while (it1 != it2) {
cout << *it1++ << ' ';
}
return ostream1;
}
void swap(vector<int> &v, int index1, int index2) {
int t = v[index1];
v[index1] = v[index2];
v[index2] = t;
}
void sort(vector<int> &v) {
// 在这里我们还是需要迭代，这里的 i1 代表的就是当前正在排序的位置
// 如果 i1 迭代结束 排序就结束了
for (int i1 = 0; i1 < v.size(); ++i1) {
// 在这里，我们需要找到从 i1 之后
// 向量中最小值/最大值（根据需求哦）对应的索引！和 i1 的位置做交换
// 这样就实现了排序咯
int minIndex = i1;
int minValue = v[i1];
for (int i = i1 + 1; i < v.size(); ++i){
if (minValue > v[i]){
// 如果有一个数值 v[i] 比目前选中的最小值还小，则代表 v[i] 是最小值
minValue = v[i], minIndex = i;
}
}
// 到这里找到最小值了 直接进行交换 把最小值堆积到前面去
swap(v, i1, minIndex);
}
}
int main() {
vector<int> v{10, 3, 4, 1, 60, 7};
sort(v);
cout << v << endl;
}
```
### 快速排序
>它的步骤如下
① 从数列中挑出一个元素，称为 “基准”（pivot）;
② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
简单来说，就是每次递归中都会找到一个基准，然后进行分区，分区之后，基准左右各自再次调用递归操作，直到左右指向同一个位置，代表结束排序！
接下来是具体的实现操作！
```
#include <vector>
#include "iostream"
using namespace std;
ostream &operator<<(ostream &ostream1, vector<int> &v) {
auto it1 = v.begin(), it2 = v.end();
while (it1 != it2) {
cout << *it1++ << ' ';
}
return ostream1;
}
// 分区函数，参数为待分区的数组arr，以及数组的起始和结束索引low和high
// 先选基准值
// 将小于的放基准值左边 大于的放基准值右边
// 然后将基准值的索引返回出去
int partition(vector<int> &arr, int low, int high) {
// 选择数组的最后一个元素作为pivot
int pivot = arr[high];
// 初始化一个指针i，用于记录小于pivot的元素的个数
int i = (low - 1);
// 遍历数组中的每一个元素
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于pivot
if (arr[j] < pivot) {
// 将当前元素与指针i指向的元素交换，即将小于pivot的元素放到数组的左侧
i++; // 增加指针i的值，表示又找到了一个小于pivot的元素
swap(arr[i], arr[j]); // 交换元素
}
}
// 将pivot元素放到其正确的位置上，即与指针i+1指向的元素交换
swap(arr[i + 1], arr[high]);
// 返回pivot元素的最终位置
return (i + 1);
}
void sort_fun(vector<int> &arr, int low, int high) {
// 当起始索引小于结束索引时，表示数组中还有未排序的部分
if (low < high) {
// 调用partition函数，返回pivot元素的正确位置，并使得pivot左侧的所有元素都小于它，右侧的所有元素都大于它
int pi = partition(arr, low, high);
// 递归地对pivot左侧的子数组进行快速排序
sort_fun(arr, low, pi - 1);
// 递归地对pivot右侧的子数组进行快速排序
sort_fun(arr, pi + 1, high);
}
}
void sort(vector<int> &v) {
sort_fun(v, 0, v.size());
}
int main() {
vector<int> v{10, 3, 4, 1, 60, 7};
sort(v);
cout << v << endl;
}
```
### 归并排序
```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> result;
ostream &operator<<(ostream &ostream1, vector<int> &v) {
auto it1 = v.begin(), it2 = v.end();
while (it1 != it2) {
ostream1 << *it1++ << ' ';
}
return ostream1;
}
void merge(vector<int> &arr, int low, int midIndex, int high) {
// 准备两个指针 分别指向 左边有序区域和右边有序区域 这里我们将中间值分配给左边
int l = low, r = midIndex + 1;
// 准备存储新数据
result.clear();
while (l <= midIndex && r <= high) {
// 获取到左边和右边的值 如果左边小就追加左边的到结果中，反之追加右边
result.push_back(arr[l] > arr[r] ? arr[r++] : arr[l++]);
}
// 追加完毕 避免左边或右边有剩余
while (l <= midIndex)
result.push_back(arr[l++]);
while (r <= high)
result.push_back(arr[r++]);
// 最后将结果写到 arr 里
copy(result.begin(), result.end(), arr.begin() + low);
}
void sort_fun(vector<int> &arr, int low, int high) {
// 计算出长度
int le = high - low;
if (le <= 0) {
return;
}
// 首先我们需要找到中间元素
int midIndex = low + ((high - low) >> 1);
// 左边右边各排序 这里会不断递归 最后会出现很多小排序 里面应该是很多小排序合并好的大排序 左边和右边是两个有序的
sort_fun(arr, low, midIndex);
sort_fun(arr, midIndex + 1, high);
// 合并
merge(arr, low, midIndex, high);
}
void sort(vector<int> &v) {
if (v.empty()) {
return;
}
sort_fun(v, 0, ((int) v.size()) - 1);
}
int main() {
vector<int> v{10, 3, 4, 1, 60, 7, -1};
sort(v);
cout << v << endl;
}
```
## 查找操作
### 二分查找
```
#include <iostream>
#include <vector>
using namespace std;
int search(const vector<int>& arr, int target) {
// 准备两个指针 代表 查找范围的索引区间
int l = 0, r = ((int) arr.size()) - 1;
// 开始进行迭代和循环 在循环中缩小区间
while (l <= r){
// 计算中间索引和中间数值
int midIndex = l + ((r - l) >> 1), midValue = arr[midIndex];
// 开始进行对比 决定要抛弃的区间
if (target < midValue) {
// 目标值比中间小，代表目标在左区间 舍弃右区间
r = midIndex - 1;
} else if (target > midValue){
// 目标值比中间大 代表目录在右区间 舍弃左区间
l = midIndex + 1;
} else {
// 这个情况代表 tar 和 基准值一样 找到索引了
return midIndex;
}
}
// 到这里代表没找到
return -1;
}
int main() {
vector<int> v{1, 2, 3, 4, 5, 6 ,7};
cout << search(v, 6) << endl;
cout << search(v, 4) << endl;
cout << search(v, 2) << endl;
cout << search(v, -2) << endl;
}
```
------
***操作记录***
作者：[zhao](https://www.lingyuzhao.top//index.html?search=4 "zhao")
操作时间：2024-07-04 16:29:54 星期四
事件描述备注：保存/发布
中国 天津
[](如果不需要此记录可以手动删除，每次保存都会自动的追加记录)
