C++高频知识点（三十四）

166. 说说冒泡排序和快排

冒泡排序

代码实现

#include <iostream>
using namespace std;// 冒泡排序函数
void bubbleSort(int arr[], int n) {//外面这个循环 是说 ：总共需要做几趟排序，可以根据swapped的取值 提前结束。//里面的循环是说：每一趟 需要做什么事情for (int i = 0; i < n - 1; ++i) {// 提前退出标志位bool swapped = false;for (int j = 0; j < n - i - 1; ++j) {if (arr[j] > arr[j + 1]) {// 交换 arr[j] 和 arr[j + 1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}// 如果本趟没有发生交换，说明数组已经有序if (!swapped) {break;}}
}// 打印数组函数
void printArray(int arr[], int size) {for (int i = 0; i < size; ++i) {cout << arr[i] << " ";}cout << endl;
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);cout << "未排序数组: \n";printArray(arr, n);bubbleSort(arr, n);cout << "排序后的数组: \n";printArray(arr, n);return 0;
}

快速排序

代码实现

还有一种以第一个元素作为基准元素的快排代码，见C++高频知识点（二十八）快排实现代码

#include <iostream>
using namespace std;// 分割函数，返回基准元素的最终位置
int partition(int arr[], int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = (low - 1); // i是小于基准元素的子数组的最后一个元素的索引for (int j = low; j <= high - 1; j++) {// 如果当前元素小于或等于基准元素if (arr[j] <= pivot) {i++; // 增加小于基准元素的子数组的最后一个元素的索引swap(arr[i], arr[j]); // 交换元素}}swap(arr[i + 1], arr[high]); // 将基准元素放到正确位置return (i + 1); // 返回基准元素的最终位置
}// 快速排序函数
void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high); // 分割点// 递归地排序基准元素左右的子数组quickSort(arr, low, pi - 1); // 左子数组quickSort(arr, pi + 1, high); // 右子数组}
}// 打印数组函数
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {cout << arr[i] << " ";}cout << endl;
}int main() {// 初始化一个数组int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);// 输出未排序的数组cout << "未排序数组: \n";printArray(arr, n);// 进行快速排序quickSort(arr, 0, n - 1);// 输出排序后的数组cout << "排序后的数组: \n";printArray(arr, n);return 0;
}

167. 大文件如何对字符串排序？

解决方案：外部排序（External Sorting）

外部排序是处理大文件排序的经典方法 ，通常采用多路归并排序（Multi-way Merge Sort）。
以下是具体步骤：

伪代码

#include <vector>
#include <string>
#include <fstream>
#include <queue>
using namespace std;
struct StringWithFile {string str;int fileIndex;bool operator<(const StringWithFile& other) const {return str > other.str; // min-heap 需用 > 实现}
};
void sortLargeFile(const string& inputFile, const string& outputFile, size_t blockSize) {vector<string> block;vector<ifstream> inputs;priority_queue<StringWithFile> minHeap;// 阶段 1：分块排序ifstream in(inputFile);string line;int blockId = 0;while (getline(in, line)) {block.push_back(line);if (block.size() >= blockSize) {sort(block.begin(), block.end());ofstream out("temp" + to_string(blockId++) + ".txt");for (const auto& s : block) out << s << endl;block.clear();}}if (!block.empty()) {sort(block.begin(), block.end());ofstream out("temp" + to_string(blockId++) + ".txt");for (const auto& s : block) out << s << endl;}in.close();// 阶段 2：多路归并for (int i = 0; i < blockId; ++i) {ifstream fin("temp" + to_string(i) + ".txt");inputs.push_back(move(fin));if (getline(inputs[i], line)) {minHeap.push({line, i});}}ofstream out(outputFile);while (!minHeap.empty()) {auto top = minHeap.top();minHeap.pop();out << top.str << endl;if (getline(inputs[top.fileIndex], line)) {minHeap.push({line, top.fileIndex});}}out.close();// 阶段 3：清理for (int i = 0; i < blockId; ++i) remove(("temp" + to_string(i) + ".txt").c_str());
}

168. 说一下MySQL的B+树

B+树是一种多路平衡查找树，是MySQL InnoDB存储引擎中索引的底层数据结构。它优化了磁盘I/O和范围查询，特别适合数据库场景。

B+树的特点

B+ 树 vs. B 树

169. C++ 中 override 和 final 关键字的作用是什么？它们的实现原理是什么？

在 C++ 中，override 和 final 是两个与继承和虚函数相关的关键字，引入于 C++11 标准。它们的主要作用是增强代码的可读性和安全性，避免因继承关系导致的错误。

1. override 关键字

#include <iostream>
class Base {
public:virtual void func(int x) { std::cout << "Base: " << x << std::endl; }
};class Derived : public Base {
public:void func(int x) override { std::cout << "Derived: " << x << std::endl; } // 正确重写// void func(float x) override; // 错误：基类没有匹配的虚函数，编译失败
};int main() {Derived d;Base* b = &d;b->func(10); // 输出 "Derived: 10"return 0;
}

2. final 关键字

修饰类

#include <iostream>
class Base final {
public:void func() { std::cout << "Base func" << std::endl; }
};// class Derived : public Base { }; // 错误：Base 被标记为 final，不能被继承int main() {Base b;b.func(); // 输出 "Base func"return 0;
}

修饰虚函数

#include <iostream>
class Base {
public:virtual void func() { std::cout << "Base func" << std::endl; }
};
class Derived : public Base {
public:void func() final { std::cout << "Derived func" << std::endl; } // 标记为 final
};
class MoreDerived : public Derived {
public:// void func() { } // 错误：func 在 Derived 中被标记为 final，不能重写
};
int main() {MoreDerived md;Base* b = &md;b->func(); // 输出 "Derived func"return 0;
}

170. 把uniqueptr move到sharedptr会发生什么?

#include <iostream>
#include <memory>int main() {std::unique_ptr<int> uptr = std::make_unique<int>(10);std::shared_ptr<int> sptr = std::move(uptr); // 资源转移std::cout << "uptr is " << (uptr ? "not empty" : "empty") << std::endl;std::cout << "sptr use count: " << sptr.use_count() << std::endl;return 0;
}

注意事项

171. i++是否为原子操作？

i++ 不是原子操作

如何保证 i++ 是原子操作？

方法 1：使用 std::atomic

C++ 提供 std::atomic，可以保证 i++ 是 原子操作：

#include <iostream>
#include <thread>
#include <atomic>
std::atomic<int> i(0);
void increment() {for (int j = 0; j < 100000; ++j) {i++;  // 原子操作++i;i=i+1;}
}
int main() {std::thread t1(increment);std::thread t2(increment);t1.join();t2.join();std::cout << "Final i: " << i << std::endl;  // 正确结果：200000return 0;
}

std::atomic 内部使用 CPU 原子指令 来保证 i++ 线程安全。

方法 2：使用 std::mutex

如果不能用 std::atomic，可以使用 std::mutex 来保证线程安全：

#include <iostream>
#include <thread>
#include <mutex>
std::mutex mtx;
int i = 0;
void increment() {for (int j = 0; j < 100000; ++j) {std::lock_guard<std::mutex> lock(mtx);i++;}
}
int main() {std::thread t1(increment);std::thread t2(increment);t1.join();t2.join();std::cout << "Final i: " << i << std::endl;return 0;
}

缺点：

• std::mutex 开销较大，因为涉及 线程上下文切换。
• std::atomic 性能更好，因为它使用 CPU 级别的原子操作

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！