【C++ 中级】 算法 题目记录

# 【C++ 中级】 算法 题目记录
*C++ 技术栏*

本文章记录了有关 C++ 数据处理 题目 和 案例 的汇总。

## 目录

[TOC]

![文章的封面](https://k.sinaimg.cn/n/sinakd20240521s/87/w1080h607/20240521/2981-ea59e6d2cf23c1fca288ae1f07b6f2d7.jpg/w700d1q75cms.jpg "文章的封面")

## 排序操作

### 冒泡排序

![](https://diskmirror.lingyuzhao.top//33/Binary//Article/Image/-87318604/1715505424221.jpg)

```
#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;
}

```

### 选择排序

![](https://diskmirror.lingyuzhao.top/DiskMirrorBackEnd/FsCrud/downLoad/33/Binary?fileName=Article/Image/-87318604/1715419516075.jpg)

这个就类似人类的排序操作，不断的寻找最值，然后追加到新容器或者旧容器中，下面就是一个示例。

```
#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）把小于基准值元素的子数列和大于基准值元素的子数列排序；

简单来说，就是每次递归中都会找到一个基准，然后进行分区，分区之后，基准左右各自再次调用递归操作，直到左右指向同一个位置，代表结束排序！

接下来是具体的实现操作！

![](https://diskmirror.lingyuzhao.top/DiskMirrorBackEnd/FsCrud/downLoad/33/Binary?fileName=Article/Image/-87318604/1715517445099.jpg)

```
#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;
}

```

### 归并排序


![Article/Image/-1018504/1720096342148.jpg](https://diskmirror.lingyuzhao.top/DiskMirrorBackEnd/FsCrud/downLoad/4/Binary?fileName=Article/Image/-1018504/1720096342148.jpg)


```
#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 星期四
事件描述备注：保存/发布
 中国 天津 
[](如果不需要此记录可以手动删除，每次保存都会自动的追加记录)