6.25小学期CPP基础语法记录：反转、字符串查找、稳定sort
<h1 id="-reverse函数">💞 reverse函数</h1><p>在 C++ 中，<code>reverse</code> 是一个非常常用的 STL 算法，用于<strong>就地反转序列</strong>中的元素顺序。它定义在 <code><algorithm></code> 头文件中。</p>
<hr>
<h2 id="-函数定义">🧩 函数定义</h2>
<pre><code class="language-cpp">template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
</code></pre>
<ul>
<li><strong>参数说明：</strong>
<ul>
<li><code>first</code>：反转范围的起始迭代器（<strong>包含</strong>）。</li>
<li><code>last</code>：反转范围的终止迭代器（<strong>不包含</strong>）。</li>
</ul>
</li>
<li><strong>返回值：</strong>
<ul>
<li>无（<code>void</code>），它是<strong>就地修改</strong>，直接在原容器上改变顺序。</li>
</ul>
</li>
<li><strong>迭代器要求：</strong>
<ul>
<li>必须是<strong>双向迭代器</strong>（如 <code>vector</code>, <code>list</code>, <code>deque</code> 都支持；<code>forward_list</code> 不支持）。</li>
</ul>
</li>
</ul>
<hr>
<h2 id="-示例">✅ 示例</h2>
<h3 id="1-反转-vectorint">1. 反转 <code>vector<int></code></h3>
<pre><code class="language-cpp">#include <iostream>
#include <vector>
#include <algorithm> // for reverse
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::reverse(v.begin(), v.end());
for (int i : v) std::cout << i << " ";
return 0;
}
</code></pre>
<p>输出：</p>
<pre><code>5 4 3 2 1
</code></pre>
<hr>
<h3 id="2-反转-string也支持因为-stringiterator-是双向的">2. 反转 <code>string</code>（也支持，因为 <code>string::iterator</code> 是双向的）</h3>
<pre><code>#include <iostream>
#include <string>
#include <algorithm>
int main() {
std::string s = "abcdef";
std::reverse(s.begin(), s.end());
std::cout << s;// 输出: fedcba
return 0;
}
</code></pre>
<hr>
<h3 id="3-局部反转">3. 局部反转</h3>
<pre><code>cpp复制编辑std::vector<int> v = {10, 20, 30, 40, 50, 60};
// 只反转中间部分 [1, 4)
std::reverse(v.begin() + 1, v.begin() + 4);// -> 10, 40, 30, 20, 50, 60
</code></pre>
<hr>
<h2 id="-reverse-的底层实现原理">🚀 reverse 的底层实现原理</h2>
<p>使用的是<strong>双向迭代器</strong>，通过交换 <code>front</code> 和 <code>back</code> 元素来实现反转。</p>
<p>伪代码：</p>
<pre><code>while (first != last && first != --last) {
swap(*first, *last);
++first;
}
</code></pre>
<hr>
<h2 id="-时间复杂度与空间复杂度">🎯 时间复杂度与空间复杂度</h2>
<ul>
<li><strong>时间复杂度：</strong> <code>O(n)</code></li>
<li><strong>空间复杂度：</strong> <code>O(1)</code>（原地操作，不使用额外空间）</li>
</ul>
<hr>
<h2 id="-举一反三">🎓 举一反三</h2>
<ul>
<li><code>std::reverse_copy(first, last, dest)</code>：把反转结果<strong>复制</strong>到另一个位置，不影响原数据。</li>
</ul>
<pre><code>std::vector<int> v = {1,2,3,4,5};
std::vector<int> res(5);
std::reverse_copy(v.begin(), v.end(), res.begin());// res = 5,4,3,2,1
</code></pre>
<ul>
<li>如果你想自己实现一个 <code>reverse</code> 函数，可以练习写模板函数操作双向迭代器。</li>
</ul>
<hr>
<hr>
<h1 id="-stringfind函数">🔍 string::find函数</h1>
<p>C++ 中的 <code>string::find</code> 是处理字符串查找的核心函数，常用于查找某个<strong>子串或字符</strong>第一次出现的位置。下面我们详细分析它的用法、变体、返回值，再拓展介绍其他常见的字符串查找函数，比如 <code>rfind</code>、<code>find_first_of</code>、<code>find_last_of</code>、<code>find_first_not_of</code> 等。</p>
<hr>
<h2 id="-一stringfind-基本用法">🔍 一、<code>string::find</code> 基本用法</h2>
<pre><code class="language-cpp">size_t find(const string& str, size_t pos = 0) const;
size_t find(const char* s, size_t pos = 0) const;
size_t find(const char* s, size_t pos, size_t n) const;
size_t find(char c, size_t pos = 0) const;
</code></pre>
<h3 id="-参数说明">✅ 参数说明：</h3>
<ul>
<li><code>str</code> / <code>s</code> / <code>c</code>: 要查找的<strong>目标字符串/字符</strong>。</li>
<li><code>pos</code>: 从原字符串的哪个<strong>位置开始查找</strong>（默认为 0）。</li>
</ul>
<h3 id="-返回值">✅ 返回值：</h3>
<ul>
<li>成功：返回目标第一次出现的位置（类型为 <code>size_t</code>）。</li>
<li>失败：返回 <code>string::npos</code>（一个极大的无符号整数，表示未找到）。</li>
</ul>
<hr>
<h3 id="-示例一查找子串">🔧 示例一：查找子串</h3>
<pre><code class="language-cpp">std::string s = "hello world";
size_t pos = s.find("world"); // 返回 6
</code></pre>
<h3 id="-示例二查找字符">🔧 示例二：查找字符</h3>
<pre><code class="language-cpp">std::string s = "abcabc";
size_t pos = s.find('b');// 返回 1，第一个 b 的位置
</code></pre>
<h3 id="-示例三未找到">🔧 示例三：未找到</h3>
<pre><code class="language-cpp">std::string s = "hello";
size_t pos = s.find("abc");
if (pos == std::string::npos)
std::cout << "not found";
</code></pre>
<h3 id="-示例四从指定位置开始查找">🔧 示例四：从指定位置开始查找</h3>
<pre><code class="language-cpp">std::string s = "abcabc";
size_t pos = s.find('b', 2);// 返回 4，跳过前面的 b
</code></pre>
<hr>
<h2 id="-二其他查找方法汇总">🎯 二、其他查找方法汇总</h2>
<h3 id="1️⃣-rfind从右往左找返回最后一次出现的位置">1️⃣ <code>rfind</code>：从右往左找（返回<strong>最后一次</strong>出现的位置）</h3>
<pre><code class="language-cpp">std::string s = "abcabc";
size_t pos = s.rfind('b');// 返回 4
</code></pre>
<hr>
<h3 id="2️⃣-find_first_of查找任一字符第一次出现的位置">2️⃣ <code>find_first_of</code>：查找<strong>任一</strong>字符第一次出现的位置</h3>
<pre><code class="language-cpp">std::string s = "hello world";
size_t pos = s.find_first_of("aeiou");// 返回 1，‘e’是第一个元音
</code></pre>
<hr>
<h3 id="3️⃣-find_last_of查找任一字符最后一次出现的位置">3️⃣ <code>find_last_of</code>：查找<strong>任一</strong>字符最后一次出现的位置</h3>
<pre><code class="language-cpp">std::string s = "abcabc";
size_t pos = s.find_last_of("ab");// 返回 4，‘b’在位置4最后出现
</code></pre>
<hr>
<h3 id="4️⃣-find_first_not_of找第一个不是指定字符集的字符">4️⃣ <code>find_first_not_of</code>：找第一个<strong>不是指定字符集</strong>的字符</h3>
<pre><code class="language-cpp">std::string s = "aaaabc";
size_t pos = s.find_first_not_of('a');// 返回 4，‘b’不是 ‘a’
</code></pre>
<hr>
<h3 id="5️⃣-find_last_not_of找最后一个不是指定字符集的字符">5️⃣ <code>find_last_not_of</code>：找最后一个<strong>不是指定字符集</strong>的字符</h3>
<pre><code class="language-cpp">std::string s = "abcddd";
size_t pos = s.find_last_not_of('d');// 返回 2，‘c’不是 ‘d’
</code></pre>
<hr>
<h2 id="-实战对比与举一反三">📘 实战对比与举一反三</h2>
<table>
<thead>
<tr>
<th>函数名</th>
<th>含义</th>
<th>查找方向</th>
<th>典型用途</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>find</code></td>
<td>第一次出现</td>
<td>左→右</td>
<td>查找特定子串或字符</td>
</tr>
<tr>
<td><code>rfind</code></td>
<td>最后一次出现</td>
<td>右→左</td>
<td>查找最后一个位置</td>
</tr>
<tr>
<td><code>find_first_of</code></td>
<td>第一次出现（任一）</td>
<td>左→右</td>
<td>查找多个候选字符之一</td>
</tr>
<tr>
<td><code>find_last_of</code></td>
<td>最后一次出现（任一）</td>
<td>右→左</td>
<td></td>
</tr>
<tr>
<td><code>find_first_not_of</code></td>
<td>第一个<strong>不是</strong>指定字符</td>
<td>左→右</td>
<td>忽略前缀空格等</td>
</tr>
<tr>
<td><code>find_last_not_of</code></td>
<td>最后一个<strong>不是</strong>指定字符</td>
<td>右→左</td>
<td>忽略后缀空格等</td>
</tr>
</tbody>
</table>
<hr>
<h2 id="-延伸用-find-实现字符串替换">🧠 延伸：用 find 实现字符串替换</h2>
<pre><code class="language-cpp">std::string s = "abcabc";
std::string from = "ab", to = "XY";
size_t pos = 0;
while ((pos = s.find(from, pos)) != std::string::npos) {
s.replace(pos, from.length(), to);
pos += to.length(); // 避免死循环
}
// s 变为 "XYcXYc"
</code></pre>
<hr>
<hr>
<h1 id="-计数排序的巧妙用法">🔢 计数排序的巧妙用法</h1>
<pre><code class="language-text">【问题描述】
定义一个字符串的无序度为所有位置后面的字母比该位置的字母小的总数之和。比如"DAABEC''这个字符串的无序度是5，因为D后面有4个位置比它小（AABC），E后面有1个比它小（C），其它位置后面没有比自己小的。" AACEDGG "的无序度为1（E后面有一个D比它小）。" ZWQM "的无序度为6，每个位置后面所有的字母都比它小。
现在你的任务是给定一些字符串（只由大写字母组成），把他们按照无序度从小到大排序，如果无序度一样，那么就按照输入的相对顺序排序。
【输入形式】
单组测试数据。
第一行有两个整数n(0 < n <= 50)和m (0 < m <= 100)，分别表示输入的字符串的长度和字符串的个数。
接下来m行，每一行包含一个长度为n的字符串，只由大写字母组成。
【输出形式】
输出m行，表示排序之后的字符串。
【样例输入】
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
【样例输出】
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
</code></pre>
<p>面对形如求逆序数的题目，常用的方法有：</p>
<ul>
<li>暴力法（省略）</li>
<li>归并排序</li>
<li>树状数组</li>
<li>线段树</li>
</ul>
<p>但对于只包含大写字母的情况，我们可以用O(n)时间复杂度的算法：</p>
<h2 id="使用计数数组的方法">使用计数数组的方法</h2>
<p>思路是从右向左遍历字符串，维护一个计数数组记录已经遇到的每个字符的数量：</p>
<pre><code class="language-cpp">// 以O(n)时间复杂度计算字符串无序度
int cal(string a){
int cnt = {0}, ans = 0;
for(int i = n - 1; i >= 0; --i){
int num = a - 'A';
++cnt;
for(int j = num - 1; j >= 0; --j){
ans += cnt;
}
}
return ans;
}
</code></pre>
<h3 id="原理解释">原理解释</h3>
<ol>
<li>从右向左遍历字符串，这样我们处理每个字符时，它后面的字符已经被处理过</li>
<li>对于每个位置i，我们统计在位置i后面出现的、比字符s小的所有字符的数量</li>
<li>使用计数数组count记录已处理的每个字符的出现次数</li>
<li>对于当前字符s，统计比它小的所有字符(A到s-1)的出现次数之和，这就是该位置对无序度的贡献</li>
</ol>
<p>这个方法的时间复杂度是O(n)，因为外层循环n次，内层循环最多26次（大写字母数量固定），所以总体是O(26n) = O(n)。</p>
<hr>
<h2 id="-完整解决方案">🌕 完整解决方案</h2>
<h3 id="---计数排序思路">🌟 🌟 🌟 计数排序思路</h3>
<pre><code class="language-cpp">#include <bits/stdc++.h>
using namespace std;
int n, m;
int cal(string a){
int cnt = {0}, ans = 0;
for(int i = n - 1; i >= 0; --i){
int num = a - 'A';
++cnt;
for(int j = num - 1; j >= 0; --j){
ans += cnt;
}
}
return ans;
}
int main(){
cin >> n >> m;
vector<pair<string, int>> strs(m);
for(int i = 0; i < m; ++i){
cin >> strs.first;
strs.second = cal(strs.first);
}
stable_sort(strs.begin(), strs.end(),
[](pair<string, int> a, pair<string, int> b){
return a.second < b.second;
});
for(int i = 0; i < m; ++i){
cout << strs.first << endl;
}
}
</code></pre>
<h3 id="--归并算法">🌟 🌟 归并算法</h3>
<pre><code class="language-cpp">// 使用归并排序计算无序度
int mergeCount = 0; // 全局变量记录逆序对数量
void merge(vector<char>& arr, int left, int mid, int right) {
vector<char> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr <= arr) {
temp = arr;
} else {
// 当右半部分元素小于左半部分时，构成逆序对
temp = arr;
mergeCount += (mid - i + 1); // 计算逆序对
}
}
while (i <= mid) temp = arr;
while (j <= right) temp = arr;
for (i = left, k = 0; i <= right; i++, k++) {
arr = temp;
}
}
void mergeSort(vector<char>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
// 计算字符串无序度
int calculateDisorder(const string& s) {
// 需要重新组织数据结构来适应我们的问题
vector<pair<char, int>> charWithPos;
for (int i = 0; i < s.length(); i++) {
charWithPos.push_back({s, i});
}
// 结果...
}
</code></pre>
<h3 id="-树状数组">🌟 树状数组</h3>
<pre><code class="language-cpp">class BIT {
private:
vector<int> tree;
int n;
int lowbit(int x) {
return x & (-x);
}
public:
BIT(int size) : n(size), tree(size + 1, 0) {}
void update(int idx, int val) {
while (idx <= n) {
tree += val;
idx += lowbit(idx);
}
}
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree;
idx -= lowbit(idx);
}
return sum;
}
};
int calculateDisorder(const string& s) {
int n = s.length();
int disorder = 0;
// 创建离散化映射(A-Z -> 1-26)
map<char, int> charToIdx;
for (char c = 'A'; c <= 'Z'; c++) {
charToIdx = c - 'A' + 1;
}
BIT bit(26); // 26个大写字母
// 从右向左遍历
for (int i = n - 1; i >= 0; i--) {
int idx = charToIdx];
// 查询比当前字符小的所有字符的出现次数
disorder += bit.query(idx - 1);
// 更新当前字符的出现次数
bit.update(idx, 1);
}
return disorder;
}
</code></pre>
<h3 id="-线段树">🌟 线段树</h3>
<pre><code class="language-cpp">class SegmentTree {
private:
vector<int> tree;
int n;
public:
SegmentTree(int size) : n(size) {
tree.resize(4 * n, 0);
}
void update(int node, int start, int end, int idx) {
if (start == end) {
tree++;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) {
update(2 * node, start, mid, idx);
} else {
update(2 * node + 1, mid + 1, end, idx);
}
tree = tree + tree;
}
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
return 0;
}
if (l <= start && end <= r) {
return tree;
}
int mid = (start + end) / 2;
int leftSum = query(2 * node, start, mid, l, r);
int rightSum = query(2 * node + 1, mid + 1, end, l, r);
return leftSum + rightSum;
}
};
</code></pre>
<hr>
<hr>
<h1 id="稳定的sort--stable_sort用法详解">稳定的<code>sort</code> —— <code>stable_sort</code>用法详解</h1>
<p>我们来系统讲解 <code>std::stable_sort</code>：不仅要理解它的功能和用法，还要深入分析它为什么叫“稳定排序”（<strong>stable</strong>）以及它背后的算法原理。</p>
<hr>
<h2 id="-一stdstable_sort-概述">🧩 一、<code>std::stable_sort</code> 概述</h2>
<pre><code class="language-cpp">#include <algorithm>
template <class RandomIt>
void stable_sort(RandomIt first, RandomIt last);
template <class RandomIt, class Compare>
void stable_sort(RandomIt first, RandomIt last, Compare comp);
</code></pre>
<ul>
<li><strong>作用</strong>：对 <code>[first, last)</code> 区间的元素进行<strong>稳定排序</strong>。</li>
<li><strong>特点</strong>：排序后，相等元素的<strong>原始相对顺序保持不变</strong>。</li>
<li><strong>迭代器要求</strong>：必须是<strong>随机访问迭代器</strong>（如 <code>vector</code>, <code>deque</code>, 原始数组等）。</li>
</ul>
<hr>
<h2 id="-二稳定排序的含义">🎯 二、稳定排序的含义</h2>
<p><strong>稳定性定义</strong>：</p>
<p>如果在排序前，两个元素 <code>A</code> 和 <code>B</code> 相等（<code>A == B</code>），并且 <code>A</code> 在 <code>B</code> 前面；排序后，<code>A</code> 仍然在 <code>B</code> 前面 → 这种排序叫做 <strong>稳定排序（stable sort）</strong>。</p>
<p>举个例子更直观：</p>
<pre><code class="language-cpp">struct Item {
int key;
char tag; // 附加标记，用于区分原始顺序
};
vector<Item> items = {
{2, 'a'},
{1, 'b'},
{2, 'c'},
{1, 'd'}
};
std::stable_sort(items.begin(), items.end(), [](Item a, Item b) {
return a.key < b.key;
});
</code></pre>
<p><strong>排序后结果：</strong></p>
<pre><code>{1, 'b'}, {1, 'd'}, {2, 'a'}, {2, 'c'}
</code></pre>
<p>注意：虽然 <code>1</code> 和 <code>2</code> 都出现了多次，但其原始相对顺序被保留。</p>
<hr>
<h2 id="️-三和-stdsort-的区别">⚙️ 三、和 <code>std::sort</code> 的区别</h2>
<table>
<thead>
<tr>
<th>特性</th>
<th><code>std::sort</code></th>
<th><code>std::stable_sort</code></th>
</tr>
</thead>
<tbody>
<tr>
<td>是否稳定</td>
<td>❌ 否</td>
<td>✅ 是</td>
</tr>
<tr>
<td>时间复杂度</td>
<td>最优 <code>O(n log n)</code></td>
<td>最优 <code>O(n log^2 n)</code></td>
</tr>
<tr>
<td>空间复杂度</td>
<td>原地排序 <code>O(1)</code></td>
<td>需要额外空间 <code>O(n)</code></td>
</tr>
<tr>
<td>使用算法</td>
<td>快速排序/混合排序</td>
<td>通常是<strong>归并排序</strong></td>
</tr>
</tbody>
</table>
<hr>
<h2 id="-四为什么-stable_sort-是稳定的">🧠 四、为什么 <code>stable_sort</code> 是稳定的？</h2>
<h3 id="-原因底层是归并排序">🔍 原因：底层是<strong>归并排序</strong></h3>
<p><code>std::stable_sort</code> 通常使用 <strong>优化版归并排序（Merge Sort）</strong> 实现，因为归并排序<strong>天然稳定</strong>。</p>
<h3 id="-稳定的原因核心在于合并过程不打乱相等元素的原始顺序">📌 稳定的原因核心在于“<strong>合并过程不打乱相等元素的原始顺序</strong>”：</h3>
<p>在归并两个有序子序列时，如果出现：</p>
<pre><code class="language-cpp">Left == Right
</code></pre>
<p>稳定排序会<strong>优先选择左边的元素（原先靠前）</strong>进入结果，确保相对顺序不变。</p>
<blockquote>
<p>所以：即使 <code>operator<</code> 或自定义比较函数 <code>comp</code> 不区分相等元素，稳定排序也不会打乱原始顺序。</p>
</blockquote>
<hr>
<h2 id="-五使用示例">🚀 五、使用示例</h2>
<h3 id="示例一默认比较">示例一：默认比较</h3>
<pre><code class="language-cpp">#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> v = {5, 3, 4, 3, 2};
std::stable_sort(v.begin(), v.end());
for (int x : v) std::cout << x << " ";
return 0;
}
// 输出：2 3 3 4 5
</code></pre>
<h3 id="示例二结构体排序强调稳定性">示例二：结构体排序（强调稳定性）</h3>
<pre><code class="language-cpp">#include <iostream>
#include <vector>
#include <algorithm>
struct Student {
int score;
std::string name;
};
int main() {
std::vector<Student> students = {
{90, "Alice"},
{85, "Bob"},
{90, "Charlie"},
{85, "David"}
};
std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
return a.score < b.score;
});
for (const auto& s : students)
std::cout << s.score << " " << s.name << "\n";
return 0;
}
</code></pre>
<p><strong>输出：</strong></p>
<pre><code>85 Bob
85 David
90 Alice
90 Charlie
</code></pre>
<p>可见分数相同的 <code>Bob</code> 和 <code>David</code> 顺序未变。</p>
<hr>
<h2 id="-六什么时候用-stable_sort">💡 六、什么时候用 <code>stable_sort</code>？</h2>
<ul>
<li>当你排序的是<strong>有多个字段的结构体/对象</strong>，先按次要字段排，再按主要字段排，并且希望<strong>次要字段顺序不被破坏</strong>。</li>
<li>举例：二次排序（先排名字，再排成绩）的时候非常有用。</li>
</ul>
<hr>
<h2 id="-时间复杂度对比分析扩展">🧮 时间复杂度对比分析（扩展）</h2>
<table>
<thead>
<tr>
<th>算法</th>
<th>最坏</th>
<th>最好</th>
<th>稳定性</th>
<th>空间</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>sort</code></td>
<td>O(n log n)</td>
<td>O(n log n)</td>
<td>❌</td>
<td>O(1)</td>
</tr>
<tr>
<td><code>stable_sort</code></td>
<td>O(n log² n)</td>
<td>O(n log n)</td>
<td>✅</td>
<td>O(n)</td>
</tr>
</tbody>
</table>
<blockquote>
<p>注意：虽然 <code>stable_sort</code> 稳定，但当你对性能要求高、数据量极大且不关心顺序时，还是推荐 <code>sort</code>。</p>
</blockquote>
<hr>
<h2 id="-总结一句话">✅ 总结一句话：</h2>
<blockquote>
<p><code>std::stable_sort</code> 使用归并排序实现，在相等元素的情况下保持它们原来的先后顺序，适用于<strong>多关键字排序、带附加信息的排序等需要顺序保留的场景</strong>。</p>
</blockquote>
<hr><br><br>
来源：https://www.cnblogs.com/Eigh18n/p/18948924
頁:
[1]