谓词：能返回 bool 值（true/false）的函数 / 表达式，就是谓词，作用是给程序定 “筛选标准”。

（POJ是很久之后提交的）

AC 后可以安心学代码了（其实是错的）

走路吃饭都想，大便时候也是拍下代码思考

这里while (nums[++l] <= pivot); while (nums[--r] > pivot);在 OJ 上无论等号咋写都 AC，可实际我发现，这样写是错的，因为会越界！例子是：1 2 3 4 5 6 7 6 5 4 3 2 7，目的就是简单的保证大于 10 不用插入，然后交换基准后：1 2 3 4 5 6 2 6 5 4 3 7 7，这样左指针一直找大于显然找不到会直接干到数组之后的内存，不信可以加cout测试直接给你干到nums[14]可是最多才nums[12]是合法的，可居然 OJ 能 AC。

即我发现尽管我已经三数取中搞成了：小，a，b，c，中（基准），大但一旦末尾那个大和基准一样，等号是否需要写就有很大不同了，当然了这个其实目的就是为了不越界！如果意义是为了搞指针指向的和基准比较这件事，完全咋写都行（之前也说过了，等号无所谓的），但这里左指针不能写等号是防止越界的，因为没写l<r，这才是重点！！写l<r的话做了越界限制才真正可以说左右指针比较的时候写不写等号都行。

再说一个，如果代码写成不分裂的while (++l <= right && nums[l] < pivot);、while (r >= left && nums[r--] > pivot);，那比如例子3 2 1，左指针干到了下标 3，越界但用不到他，没事，可右指针本该在第一次的判断里停在下标 2 数字 1 的位置，但附带一个--直接干到了下标 1 数字 2 的位置。

备注：

mid = left + (right - left) / 2 可以避免 mid = (left + right) / 2 中 left + right 超出 int 范围导致整数溢出的问题。

所以完美闭环！

然后不存在左右指针互相大小的参与，所以可以交换左右指针的顺序。

而除了左指针语句必须写等号外，那所有涉及到等于的说白了就是可以当作小于基准或者大于基准，然后实际交换与否导致的结果就是左侧小于等于基准或者小于基准。

（相当于勘误吧）我给他代码做个优化，除了顺序以外，等号也随心所欲的加或者不加，则从low的下一个开始扫，int i = low + 1;则后面左右指针的语句无论顺序还是等号都可以想咋写咋写，然后插一句依旧是说过的东西，我理解每次都是走一步，所以只要i==j则需要退出，即把左右指针里的边界改为i==j，再次印证错误，反例1 2 3，i在下标 1 的数据 2 停下，j起初在下标 2 的数据 3 然后继续走，走到下标 1 的数据 2，此时直接i==j直接break，立马变为2 1 3。（更新：可用平台数据真的太垃圾了！！这里low + 1且左右指针都是不写等号可以 AC，但完全是错的啊，因为2 2 2这组数据直接死循环）

再说下百度百科除了严蔚敏的另一个写法：

我学到的是，此文搜++l <= right那里我无论写是否有等号都不行，因为++l已经是越界的l了，所以我就只能想到的是，既然交换用不到l，就直接没管，而右指针就搞出界又++搞了回去，

而严蔚敏的写法牛逼之处就是搞了break，但没用上天然的大小关系，

然后现在这个写法更牛，又学到了新东西，其实和之前那个三数取中差不多，三数取中如果首、尾、基准一样大就会越界，所以是否有等号依旧不能随便写，但却在思路上开了个头，因为首、基准、尾一定是一个比一个大的，天然判断完的一个结果，只不过一样大这种情况就不行了，那这个代码是：

void Qsort(vector<int>& number, int first, int last)
{
    int i, j, pivot = first;
    int temp;
    if (first < last){
        pivot = first;
        i = first;
        j = last;
        while (i < j){
            while (number[j] > number[pivot])
                j--;
            while (number[i] <= number[pivot] && i < last)
                i++;
            if (i < j)
                swap(number[i],number[j]);
        }
        swap(number[j],number[pivot]);
        Qsort(number, first, j - 1);
        Qsort(number, j + 1, last);
    }
}

这里此文搜“（相当于勘误吧）”

通过这个我总结出两种大体代码思路，

• 要么边界控制好（严蔚敏的break或者我的此文搜【思路感觉稀碎】 ），然后顺序和等号随心所欲想咋写咋写。

• 要么通过是否带等号来间接控制边界，比如这里的首位基准，右指针l判断的时候就不写等号，则l往左扫的时候最多走到基准，j为0，然后左指针往右扫，最大走到last即右边界。

但这里我发现个事，也就是我更新的此文搜“可以 AC，但完全是错的啊”（我发现这个事是因为之前 AC，但这个代码发现有边界我就去掉i的等号，直接 TLE），我一直以为从基准的后一位开始扫就会解决等号的问题，但发现还是对算法本质不理解，因为左指针从哪里开始扫完全不影响只要略过基准别把基准交换走了就行，而等号的事：

• 写等号那比较时候遇到纯大/小就停止，但注意如果后进行自增自减，可能会越界，所以要控制边界。

• 不写等号则遇到等于的也停止，我一直以为就不需要控制边界了，可以完全没想到，事实是2 2 2会起手就不走，直接死循环（一侧有等号、另一侧没有等号没事）

导致我一直以为两个事（其实是错的）：

• 右指针那里相当于把之前的三数取中给做了完善，

• 左指针相当于把此文搜“再说一个，如果”，在有了严蔚敏的基础上又贴切的完善了下，因为严蔚敏“浪费”了天然大小这个关系。

总结就是（像个傻逼废物一样的应试高手去背代码的话，快排很简单，其他算法难，但细节、原理彻底透彻精通的话，快排 > 搜索、最短路、最小生成树、KMP、并查集）：

• 代码写等号后，自增自减注意边界 

• 代码不写等号注意全相同数据会死循环（但像这里一侧有、另一侧没有也是可以的，比如这里如果j死那不动，i会一路要么不停走，要么去和j交换完继续走）

• 左右指针互相之间别参与大小比较

• 然后关于顺序本来是没顺序的，保证好边界，别把左右指针互相之间参与大小比较就不会有顺序问题，即顺序没要求。

为了验证，我发现一侧没等号，那另一侧必须加上，比如：

while (number[j] >= number[pivot] && j-1>=first)  j--;、while (number[i] < number[pivot] && i < last)  i++;，依旧 AC（尽管 AC 不代表绝对正确，妈逼的累了）

那我【思路感觉稀碎】 那个代码为啥也 AC 了且实测2 2 2没事，因为++l最终就是越界风险操作，因为先自增了，导致每次都会l往前推进，所以不会死循环。

彻底精通快排！！妈逼的绞尽脑汁想破脑袋想了 14 天，所有可能的边角问题。

所有涉及到等号可以随便写的都是错的，懒得再修改博客完善了！好累~~~~(>_<)~~~~

注意重点是思路！说这些是为了表述、为了解释、练脑子、想细节！而不是记什么先左后右这种结论。 

无意间看到一个 小龙虾 的公众号文章

疑惑和感悟

wx搜：

1、诋毁

2、隐藏气质气场经历

3、服务员。架子

我就一台电脑（差生文具多）我跑步从不买鞋，就普通的。很多人跑步买鞋。

这鸡吧玩意有啥用啊，CRUD 而已啊，会一堆框架只是使用者啊，底层原理呢？自己的价值呢？

我一个没工作的，都能发现大模型 70% 都是错误，误人子弟，还他妈咋在工作公司项目中用啊？公司究竟啥水平的代码啊？连我自己几十行练手的代码都反复无穷无尽的错误。

AI 永远是给牛逼的人更牛逼，给平庸的人变得不那么平庸，而不是把海厚海厚的平庸傻逼变成牛逼，现在靠 AI 太多傻逼涌现出来，没 AI 时候，他们都干嘛的？AI 就他妈是噱头，就是适合商业、骗政府钱，割（中国 99% 都是）没脑子的人韭菜用的

鱼皮的广告（岗位区别、八股文占比）

面试需要看的东西

2026/4/8到期，但3月有活动，直接2核2G4M一年99的活动，昨天3/31买了，一系列关于龙虾的问题：

辱骂99%无脑的人、购买成功页面包含后续AI便宜的拓展、说自动在小红书干活点进去完全没有、妈逼的拼团居然是自己找人。

之前图库收藏小林coding说 C++ 硬核的坑位极少，吴师兄说那些推倒数学的都是Deepseek级别的大模型

我一意孤行，豆包也说确实很少招

25年3月试用一个月

25年4月8日买一年新人68，2核2G3M

26年4/8到期，但3月末截止的优惠是99一年，2核2G4M，如果之前续费要250元

公网变化

旧的

新的

起手先本地cmd：ssh root@82.157.107.148，发现无需输入密码直接登上了，因为C:\Users\GerJCS岛\.ssh有id_rsa.pub公钥和id_rsa私钥，公钥之前手动上传到服务器，新服务器镜像直接可以延用。

VScode里只要改下IP即可，.ssh 是个专门放 SSH 所有东西的系统文件夹，是 SSH 工具自动生成的：

• id_rsa → 你的私钥（钥匙）

• id_rsa.pub → 你的公钥（锁）

• config → VSCode 用的服务器地址配置

• known_hosts → 你连过的服务器记录

• authorized_keys → 这个只有服务器上才有，本地不会有

然后重新连接就好了 

sort遵循 “左闭右开” 规则，即[起始位置, 结束位置)

int arr[] = {3,1,2}; // 长度3，元素是arr[0],arr[1],arr[2]
sort(arr, arr+3); // 终点是arr+3（指向arr[3]，不存在），实际只排序arr[0]到arr[2]

容器（如 vector）：end ()（终点不包含）

vector<int> vec{5,4,3}; // 元素是vec[0],vec[1],vec[2]
sort(vec.begin(), vec.end()); // end()指向vec最后一个元素的下一个位置，实际排序vec[0]到vec[2]

说下比较函数：std::sort默认升序是自身规则，std::greater<>()是库自带的降序参数。几种写法：

#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>// 必须包含此头文件（部分编译器可省略，但规范要加）
using namespace std;

bool compareDesc(int a, int b) {
    return a > b; // 逻辑和lambda完全一致，只是抽成独立函数
}

// 几种等价写法
int main() {
    //默认都是升序
    int arr[] = {3,1,2};
    std::sort(arr, arr+3); // 数组：[首地址, 尾后地址)
    for(int num:arr)cout<<num;cout<<endl;//1 2 3
    
    std::vector<int> vec{5,4,3};
    std::sort(vec.begin(), vec.end()); 
    for(int num:vec)cout<<num;cout<<endl;//3 4 5
    
    //降序
    vec = {5,2,9};
    std::sort(vec.begin(), vec.end(), std::greater<int>());//降序
    for(int num:vec)cout<<num<<" ";cout<<endl;//9 5 2
    
    vec = {5,2,9};
    std::sort(vec.begin(), vec.end(), compareDesc);//降序
    for(int num:vec)cout<<num<<" ";cout<<endl;
    
    vec = {5,2,9};
    std::sort(vec.begin(), vec.end(), [](int a, int b){return a > b;});//降序
    for(int num:vec)cout<<num<<" ";cout<<endl;
}

追问豆包真爽，我全程追问豆包，没钱买书，好奇别人咋学的？

sort仅支持随机的，数组可以直接用sort：数组本身没有迭代器，但sort支持指针（数组名退化为指针），写法：

int arr[] = {5,2,9,1};
std::sort(arr, arr+4, std::greater<int>()); // arr是首地址，arr+4是尾后地址

• ✅ 支持的容器：vector、string、数组（连续内存）、deque（双端队列，连续内存）；

• ❌ 不支持的容器：list（链表，非连续内存）、map/set（自带排序规则，不用 sort）；

原因：std::sort要求底层是随机访问迭代器（能快速跳转到任意位置），只有连续内存容器满足，链表这类只能用自身的sort成员函数（如list.sort()）。

指针本身不限制指向连续内存，它只是存储内存地址的变量，能指向任意合法地址（连续数组、零散变量、链表节点都可以）。

但指针的p+i/p++这类算术操作，只有在指向连续内存时才有逻辑意义：

• 连续内存（数组）：p+3 精准指向偏移 3 个元素的地址，是有效的随机访问；

• 非连续内存（链表 / 零散变量）：p+3 会算出一个无效地址，操作无意义。

简言之：指针可指向任意地址，但随机访问能力仅对连续内存有效。

指针是 “内存地址的直接指向”，迭代器是 “容器元素的逻辑指向”（底层适配容器实现）。

支持随机访问 == 连续内存

内存不连续的list，it++是链表下一个节点的地址，

内存连续的vector，it++是

2、qsort：C 标准库函数，基于 void 指针，无类型安全，需自定义比较函数，底层是快排，支持任意连续内存数据

#include <stdlib.h>
#include<iostream>
using namespace std;
// 比较函数：返回<0则a在前，>0则b在前，=0则顺序不变
int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b; // 升序
}
int main() {
    int arr[] = {3,1,2};
    qsort(arr, 3, sizeof(int), cmp); // 数据首地址、元素个数、单个元素大小、比较函数
    //1 2 3
}

void* 类型转换：qsort 的比较函数参数是 const void*，这是 C 语言为了通用化设计的无类型指针，必须强制转换成具体类型（如 int*）才能解引用（*(int*)a），否则无法访问数据值。

qsort 函数参数逻辑：

• arr：待排序数据的起始内存地址（C 语言中数组名退化为指针）；

• 3：数组元素总个数（必须手动指定，sort 靠迭代器区间自动计算）；

• sizeof(int)：单个元素的字节大小（qsort 不知道数据类型，需告知内存占用，sort 靠模板推导）；

• cmp：函数指针，这个逼玩意贼智障，规则是说：

  • 差值< 0第一个参数在第二个参数前面

  • 差值> 0第一个参数在第二个参数后面，

比如return *(int*)a - *(int*)b;就是升序，return *(int*)b - *(int*)a;就是降序。

相当傻逼！！当年 C 语言设计 qsort 时，就想让比较函数直接返回正负来表示顺序，省掉多余判断，所以就定成：

• • 负数 → 第一个参数放前面

  • 正数 → 第二个参数放前面

用减法刚好能一步出正负，就这么沿用下来了

• • 若 a=3，b=5：a - b = -2（负）→ a 在前，升序

  • 若 a=5，b=3：b - a = -2（负）→ b 在前，降序

qsort第一个参数是接受地址：

传递数组名字会隐式转为void*，传递vector要写vec.data()，返回int*，即qsort(vec.data(), vec.size(), sizeof(int), cmp);。

vec.data() 是 C++ 中vector容器的成员函数，返回指向 vector 底层连续内存数组起始位置的指针，类型为对应元素类型的指针，比如vector<int>的data()返回int*。

必须保证指针指向的内存是连续的，否则 qsort 通过指针 + 偏移访问元素会直接出错。但别qsort和容器混用，丢安全性。

补充：

• 规则：一元运算符（++/--）优先级高于关系运算符（<），二元运算符（+）优先级也高于关系运算符；前缀 ++（++i）先自增再参与运算，后缀 ++（i++）先参与运算再自增。

• i++<10：先用i的原值和 10 比较，比较完成后i再自增 1。i+1<10：先计算 i+1 的结果。

3.8、既然说到排序直接整个大厂需要会的排序都学下吧

插一句，POJ 那个题目，如果不用快排等算法，暴力的话，数据量是10⁴，挨个数（记作 x）遍历一遍数据量总数，然后统计比 x 大的和比 x 小的，相等才行，总共 10⁸ 直接 TLE

OJ 1s 有效运算量上限约10^8次（理想是10^9），若后台数据 100 组，则代码写出的单组数据的运算量必须 10^6 内，所以这里

发现算法其实无法提高智力，只是术业有专攻，熟能生巧，就比如搜索算法改写暴力for我都感觉不会，因为没这么想过。

妈逼的插入也这么精密，看着简单，细节和边界条件很多

算法思路理解起来很简单，难的是代码怎么卡住边边角角达成算法思路

说插入排序：

比如升序，思路就是拿首位当排好序的，然后从第二位开始遍历后面每个元素，每次遍历都做一件事：和前面的比较，比前面小则前面那个元素就往后移动，移动完找到正确位置，把当前元素插进去。

比如3 6 2，

先拿 3 当作排序好的，

先取 6，6 和 3 比不动，

然后 2（先放到个变量存起来），2 < 6，6 往后挪，变为 3 6 6，此时第一个 6 是没用的坑位，给前面挪动准备的，

然后看 3 > 2，3 往后挪，3 3 6，此时第一个3是没用的坑位，然后 2 放到 3。

非常简单看代码：

#include <iostream>
#include <vector>
using namespace std;

// 插入 升序
void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    // 从第二个元素开始，逐个向前插入
    for (int i = 1; i < n; ++i) {
        int key = arr[i];  // 当前待插入的元素
        int j = i - 1;     // 已排序区间的末尾指针

        // 向前遍历已排序区间，找到插入位置
        while (j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];  // 元素后移
            --j;
        }
        arr[j + 1] = key;  // 插入到正确位置
    }
}
int main() {
    std::vector<int> arr = {1, 3, 6};
    insertionSort(arr);
    for (int num : arr) std::cout << num << " ";cout<<endl;
}

捋一遍：

首位先定死，然后i作为指针选第二个开始搞，值先存到key，需要和前面的比较，则i前面的都是有序的，j设成i-1，j只要没扫到头就一直扫，做比较arr[j] > key，然后判断是否后移，key位置已经腾出来了坑位，前面的放心后移即可，移动完那前面本身的位置又当作新的坑位，

此时需要注意如果比较到头就可以停， 说明已经找到该放的位置了，但代码的写法要注意，一旦j < 0，就该退出while了，那此时j+1就是该放的位置，如果< 0那就是该放到首位，除此之外就是在前面一堆数的某个位置停下，那一定是arr[j] < key，不挪动，则直接放到此时j的后一个即可！也就是上一次留下的坑位，所以有arr[j + 1] = key;。

时间复杂度： 

• 最坏两层循环都执行到最后，总操作：

第 1 次：内层跑 n-1 次

第 2 次：内层跑 n-2 次

第 3 次：内层跑 n-3 次

...

最后 1 次：内层跑 1 次

复杂度 ；

• 最好数组已有序，内层循环不走，复杂度 。

啥时候用？

大规模数据用快排，无法事先知道是否有序，所以 有序也没招

小规模数据，用插入因为 n² 大不到哪去，且没有递归、没有分治、没有额外函数调用开销

太多思考就此作罢，这些都是工业学术研究完的，不需要考虑 n² 和递归哪个更耗时 。

3.9、归并

插一句：

 博客园标题黑了（之前蓝色的）。

vector几种声明：

vector<int> a;空容器，一个元素都没有。

vector<int> a(N);创建 N 个 int，默认值都是 0。

vector<int> a(N, val);创建 N 个 int，每个值都是 val。

vector<int> a(arr, arr+N);把数组前 N 个元素拷贝进 vector。

vector<int> a{a,b,c};直接存入 a、b、c 三个元素。

vector是动态的，所以直接范围for就是全部，而如果开 1000 个静态数组，但只用了前 N 个位置，想输出前 N 个，没法范围for，但可以引入vector：

• 要么临时的没名字：for(int num : vector<int>(arr, arr+N)) cout << num << " ";，进入 for 循环前创建一次临时对象比如叫 haha，整个 for 循环期间全程只用这一个 haha，循环结束后：haha 立刻自动销毁

• 要么vector<int> temp(arr, arr+N); 、for(int num : temp) cout << num << " ";。

vector自己会自动销毁、自动释放内存。

开始说归并（实测可用平台可以 AC）

#include<iostream>
using namespace std;

// 合并 arr[l~mid] 和 arr[mid+1~r]
void merge(int arr[], int l, int mid, int r) {
    int i = l;       // 左区间起点
    int j = mid + 1; // 右区间起点
    int k = 0;
    int* tmp = new int[r - l + 1]; // 开一个临时数组存合并结果

    // 两边都还有元素，比大小，小的先放进临时数组
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];//左边小，放左边的
        else
            tmp[k++] = arr[j++];
    }
    //剩余元素的处理
    //把左边剩下的元素直接放进去
    while (i <= mid) tmp[k++] = arr[i++];
    
    // 把右边剩下的元素直接放进去
    while (j <= r) tmp[k++] = arr[j++];
    // 拷贝回原数组
    for (i = l, k = 0; i <= r; i++, k++)
        arr[i] = tmp[k];

    delete[] tmp;
}

// 8 4 5 7 1 3 6 2

// [4 999]   [5 7 8]


void mergeSort(int arr[], int l, int r) {
    if (l >= r) return;//最后局面是两个数的也会被搞成一个数，一个数的再次 mergeSort 才是 l > r 所以直接在一个数的时候 == 就 return 也可以，实测依旧 AC
    int mid = (l + r) / 2;  //奇数：mid是第一堆尾巴，偶数：mid是中间
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
} 

int N;
const int MAX=10000;//C++ 静态数组大小必须是编译期常量，非 const 变量无法作为数组长度，报错
int arr[MAX];
int main() {
    while(scanf("%d", &N) != EOF){
        for (int i = 0; i < N; i++) cin >> arr[i];
        
        mergeSort(arr, 0, N-1);
        for(int i=0; i<N; i++) cout << arr[i] << " ";cout<<endl;
        
        // cout<<arr[N/2]<<endl;
    }
}

归并思路就是 ：数组：[8,4,5,7,1,3,6,2]

第一步：拆分（不停二分，拆到单个元素）

总长度 8，永远从中间拆分

1. 第一次拆：左 [8,4,5,7] | 右 [1,3,6,2]

2. 第二次拆：[8,4] | [5,7] | [1,3] | [6,2]

3. 第三次拆：[8] | [4] | [5] | [7] | [1] | [3] | [6] | [2]

   拆分结束！规则：只要长度 > 1，就中间拆分；长度 = 1，停止拆分。

第二步：合并（两个有序数组，按大小合并成一个新有序数组）

合并规则：

1. 两个指针分别指向两个数组开头

2. 谁小拿谁，放进结果

3. 一个数组拿完，把另一个剩下的直接全拿过来

4. 合并完的数组一定是有序的

合并演示：

合并 [4] 和 [8] → 比大小 → [4,8]

合并 [5] 和 [7] → 比大小 → [5,7]

合并 [1] 和 [3] → 比大小 → [1,3]

合并 [2] 和 [6] → 比大小 → [2,6]

上一层：

合并 [4,8] 和 [5,7]

4 vs 5 →拿 4；8 vs 5→拿 5；8 vs 7→拿 7；最后拿 8 → [4,5,7,8]

合并 [1,3] 和 [2,6]

1vs2→拿 1；3vs2→拿 2；3vs6→拿 3；最后拿 6 → [1,2,3,6]

最后一层：

合并 [4,5,7,8] 和 [1,2,3,6] → 最终有序 [1,2,3,4,5,6,7,8]。

归并的时间复杂度：n * logn，解释：

配合代码：

比如[4, 1, 3, 2]，在mergeSort里的流程是：

先起手把[4, 1, 3, 2]塞进mergeSort，记作 1 层，1 层里mergeSort(arr, l, mid);把[4，1]搞进 2 层递归，[4，1]把[4]搞进 3 层递归，由if (l >= r) return;直接判断返回 2 层，2 层里该执行mergeSort(arr, mid + 1, r);语句了，把[1]搞进 3 层递归同理返回（有点 DFS 深搜的感觉），此时 2 层里[4，1]该执行代码语句merge(arr, l, mid, r);，这个最后看，只当作排序即可，出来变成[1，4]，该层结束返回到 1 层，

1 层该到语句mergeSort(arr, mid + 1, r);了，同理搞成是[2，3]，

然后执行 1 层里的merge(arr, l, mid, r);语句，此时是[1，4，2，3]来合并做排序，搞排序就成了[1，2，3，4]，递归这么想一遍就懂了，格式不清晰，看不懂可以看 豆包加工版。

插一句此时回忆：

• 分治（拆成独立子问题分别解再合并）：之前学过的将任务分给大和尚，大和尚分给小和尚，小和尚分给小小和尚，逐级完成任务提交给大和尚就完事

• 贪心：每步选当前最优，就是全局最优

• DP：

  • 没有重复子问题 → 不用 DP，直接分治就行

  • 有大量重复子问题 → 用 DP 存结果，避免重复计算，才能高效算出全局最优

  背包问题里：dp[i][j] 会被后面无数状态反复用到，这就是重复子问题，搞到全局最优，但不重复计算是让算法变快（高效），重复计算 = 算法变慢，但结果依然是最优。

然后看merge(arr, l, mid, r);，例子的[4，1，3，2]已经在每次的分段搞成了[1, 4]、[2, 3]，进入merge(arr, l, mid, r);：

• 左段：l=0, mid=1 → [1，4]

• 右段：mid+1=2, r=3 → [2，3]

while (i <= mid && j <= r)限制每段的数据，1，2，3，4逐步加到新数组。

唯一需要思考的就是剩余元素的处理，为啥直接填到尾部，比如[4 999]、[5 7 8]，此时加完 4 会加 5，然后 7、8，注意此时加完 8，指针就移动到了外面就该退出了，那剩下元素就是 999，直接加到最后，我的思考：难道 999 不可能比 7、8 小吗？这里确切属于看出确实 999 最大，那如果是 a b c 呢？其实这两段属于有个前提，一定自身都是有序的，左右各自的指针一旦有一个移动出界了，那没遇到的一定都是比这个大的！所以直接无脑接上就好。

然后豆包说不考但给我扯了个非递归版本（也叫迭代版，用for 循环控制步长，手动拆分，不调用自身，无栈溢出风险，工程上处理大数据更安全），但说大厂不考但我一意孤行的学了

void mergeSortIter(int arr[], int n) {
    // len = 当前要合并的【小块长度】
    // 从1开始，每次翻倍：1→2→4→8→...直到覆盖整个数组
    for (int len = 1; len < n; len *= 2) {//123的1

        // 两两一组合并：左块起点字母 l，左块长度 len
        // 下一组跳 2*len
        for (int l = 0; l + len < n; l += 2 * len) {//字母l

            int mid = l + len - 1;    // 左块末尾
            int r = min(l + 2*len -1, n-1);  // 右块末尾（不越界）

            merge(arr, l, mid, r);    // 合并这两段！
        }
    }
}

流程：

比如4 1 3 2 6 5，起手动作for (int len = 1; len < n; len *= 2) {，意思是长度先从 1 开始，其实是递归版的逆过程，递归版是最后拆分到了 4 和 1，这里起手就搞 4 和 1，

也就是先搞4 1成为1 4，然后搞3 2成2 3，然后搞6 5成5 6，即1 4 2 3 5 6，

然后下一轮 for，len变成 2，相当于把这次的两个小块（len=1）给直接当作一个大块了，搞的是[1，4]和[2，3]，搞成[1，2，3，4]，然后此时左指针l该移动+4了也就是到数字 6，然后+2，

注意先说下为啥要l + len < n，是判断是否存在右段可以和左段合并，没有就不合并，l + len是右区间起点，只有它小于n才代表存在右区间可以合并，且不需要保证完整右段，l + len < n 只需要保证右段至少有 1 个元素就能合并。

所以此处发现+2就不满足<n了，则直接退出，事实上也是只剩下左段的5,6，此时就是刚搞好的1，2，3，4和没搞的5，6，

然后进入len是 4，搞的就是他俩。

PS：快排也有非递归版本，都是防爆栈的，这玩意大厂说不考，我辱骂豆包我说你妈逼的狗东西，以后不考就不提及，你只要说了我（强迫症）就得看。

差别：

• 递归归并，是函数自己调用自己（递归），用系统栈，系统自动管理的调用栈（系统栈，空间小，深了会爆栈），关键就是每次调用都新开一份变量，层层叠加，占内存越来越多，会爆栈。

必须保存每一层状态，所以要压栈。递归会不断叠加函数调用栈（深度涨）

• 手动写 stack 容器 / 数组存数据，用手动栈，空间极大，不会爆栈，此处的for非递归版是，从头到尾只用一份变量，循环覆盖复用，不新增、不叠加，永远不爆栈。

for 循环顺序执行，不回头，不回溯，不需要保存历史状态，自然不压栈。栈深度固定为 1。

Q：妈逼的别他妈这么乱套行吗！！老子脑瓜子笨！！没看出到底啥区别？不都是在栈吗？

A：for循环 和 递归 里的所有局部变量（len/l/mid/a…）全都在栈区，这一点完全一样，区别根本不在于 “变量存在哪”，而在于 “函数调用栈压了多少层”。

• 递归：函数自己调用自己 → 每递归一次，系统栈就多压一层，层数会涨到 logN，会爆。

• 非递归的for 循环：永远只有一层函数调用，循环千万次也不会多压一层栈，栈深度永远 == 1，绝对不爆

Q：是否递归时间复杂度还他妈能变？？

A：时间复杂度 O (nlogn) 是计算次数，和系统栈深度是两个完全无关的概念：

• 递归：栈深度 = logn（会溢出风险）

• 非递归：时间复杂度同样 O (nlogn)，但系统栈深度 = 1（无风险）

Q：底层是为啥？

A：内存分为：

1. 栈（系统栈）：函数调用、局部变量 → 空间小 → 递归会爆

2. 堆：new 出来的 → 空间大

3. 全局 / 静态：代码外面定义的数组 → 空间超大，绝不会爆栈

递归为什么会爆？每次执行 DFS(...)，系统必须自动压入：

• 函数参数

• 函数返回地址

• 局部变量

• 寄存器状态

一调用就压一大段！系统栈只有几 MB，递归几千层 = 直接爆！

非递归为什么不爆？你自己写：int st[100000]; 是全局 / 静态数组，或者stack<int> st; 对象本体在栈，里面存的数据在堆，这些不在系统栈里！空间巨大，存 100 万都没事！

至此突然回忆起之前 刷算法题，那时候是有大学基础，然后离职自学C++之前（为了建立自信、进入学习状态、有学习节奏）刷的时候，就强迫症回忆两种写法（仅仅是手写数组模拟队列 VS queue），当初单纯的以为是手写和库的区别，以为手写更锻炼思维，库是现成的，但其实对于广搜确实是如此，而这个引出了深搜，其实当时我并不知道，真正不同就是深搜，进一步说，

• DFS：可递归（函数自调）/ 非递归（手写数模拟栈或者stack都行）

• BFS：只有非递归，必须用队列，队列实现：可用 C++ queue 或数组模拟，两种都算非递归 BFS，都不爆栈。

所以之前 BFS 写了手写模拟的，但真正不同或者说有意义的是 DFS 也手写即用非递归

另一个 题目 用到了stack栈，但只是存路径，不是非递归的DFS。

再次科普点东西：

• 数据结构：队列（先进先出）、栈（先进后出）：是逻辑结构，手写模拟 = 非递归；

• 堆：是内存区域（new/malloc），和栈 / 队列不是一类东西，没有模拟堆这种说法；

只有两种逻辑结构：队列、栈，堆是内存不是数据结构。这里的栈只是一种逻辑结构，跟放哪没关系

数据结构意义上的栈，和内存区域的栈段、堆段是两回事。

• 程序默认栈段空间很小，通常几 MB，递归用的调用栈就存在这里，深度大了会栈溢出。

• 非递归，根本不一定要用栈结构，你那段迭代代码只用循环和变量，不存在栈溢出；就算用现成的栈比如std::stack，也是存在堆内存上的栈结构容器，空间接近无限，不会溢出。

• 不是栈结构就小，是系统栈段小；堆内存空间上的栈容器（指的是栈这个数据结构，实现 “后进先出” 的工具类）空间极大。

总结：

• 栈结构：是逻辑行为（后进先出）。

• 栈段 / 堆段：是内存放哪。

• 堆上的栈 = 在堆内存上，实现了栈这种数据结构。

  名字撞车了，所以你才懵。

继续深入抽插，递归是在不断压函数栈帧，几 KB / 次，深度 10^4 就超线程栈（默认≈8MB）直接爆。

手写数组 / 显式 stack 都是非递归，其中stack底层实现是开在堆（new/malloc/vector）就不在系统线程栈，自然不爆；而手写数组即使在栈（比如哪怕开10^6数组），也只是一次分配，不是递归式累积压栈，只要别开超大数组就不会爆。

所以唯一需要再学个非递归的 DFS，再来最快走一遍搜索：

DFS 递归版：

#include <stdio.h>
void dfs(int x) {
    if (x == 3) {
        printf("到终点了，返回！\n");
        return;
    }

    printf("从 %d 去 %d\n",x, x+1);
    dfs(x+1);          // 往下走
    printf("回到 %d\n", x); // 回溯！回来了！
}

int main() {
    dfs(1);
}

/*
root@VM-8-2-ubuntu:~/cpp_projects_2# ./sort
从 1 去 2
从 2 去 3
到终点了，返回！
回到 2
回到 1
*/

DFS 非递归版（stack库）：

起手豆包给的是：

#include <stdio.h>
#include <stack>
#include<iostream>
using namespace std;

int main() {
    stack<int> st;
    st.push(1);

    while (!st.empty()) {
        cout<<"新while"<<endl;
        int x = st.top();
        st.pop();

        if (x == 3) {
            printf("到终点了，返回！\n");
            continue;
        }

        printf("此时的 %d 弹出了，准备压入 %d\n", x, x+1);
        st.push(x+1);
        printf("弹出 %d\n", x);
    }
}
/*
root@VM-8-2-ubuntu:~/cpp_projects_2# ./sort
此时的 1 弹出了，准备压入 2
弹出 1
此时的 2 弹出了，准备压入 3
弹出 2
到终点了，返回！
root@VM-8-2-ubuntu:~/cpp_projects_2# 
*/

一顿质疑后发现，是伪 DFS、伪回溯，本质只是单向迭代，不是真正的DFS/回溯：

• 每次只压一个子节点，栈永远只有 1 个元素，就是一条路走到黑，无分支、无回溯、无多层状态恢复，线性迭代，不是 DFS。

追问下自己写了个，且发现 3 会进入多次，自己加了个剪枝，即真正 DFS：

• 压多个子节点，才有多条路径，弹出顺序才是深度优先，才有回溯的意义。

#include <iostream>
#include <stack>
#include<vector>
using namespace std;
int main() {
    stack<int> st;
    vector<bool> vis(5, false);//做剪枝，否则某点会访问多次

    st.push(1);
    vis[1] = true;
    cout << "初始入栈: 1" << endl;

    while (!st.empty()) {
        int cur = st.top();
        st.pop();

        printf("%d 出栈并遍历\n", cur);
        if (cur >= 3) {
            cout << cur << " 达到上限，不再压入，直接返回" << endl;
            continue;
        }
        if(vis[cur + 1] == false){
            st.push(cur + 1);
            vis[cur + 1] = true;
            printf("%d 入栈\n", cur + 1);
        }
        if(vis[cur + 2] == false){
            st.push(cur + 2);
            vis[cur + 2] = true;
            printf("%d 入栈\n", cur + 2);
        }
    }
    cout << "DFS 遍历完成" << endl;
}

/*
root@VM-8-2-ubuntu:~/cpp_projects_2# ./sort
初始入栈: 1
1 出栈并遍历
2 入栈
3 入栈
3 出栈并遍历
3 达到上限，不再压入，直接返回
2 出栈并遍历
4 入栈
4 出栈并遍历
4 达到上限，不再压入，直接返回
DFS 遍历完成
root@VM-8-2-ubuntu:~/cpp_projects_2# 
*/

PS：剪枝的地方狗逼豆包误人子弟，但我问多了知道咋及时止损，利用豆包给语法提示，剩下的有能力自己快速补

DFS 非递归版（手写数组模拟stack栈）：

#include <stdio.h>
#include<vector>
using namespace std;
int main() {
    vector<bool> vis(5, false);//剪枝

    int st[5], top = 0;
    st[++top] = 1;
    vis[1] = 1;

    while (top > 0) {
        int cur = st[top--];
        printf("%d 出栈并遍历\n", cur);

        if (cur >= 3) {
            printf("%d 达到上限，直接返回\n", cur);
            continue;
        }

        if (!vis[cur + 1]) {
            vis[cur + 1] = true;
            st[++top] = cur + 1;
            printf("%d 入栈\n", cur + 1);
        }
        if (!vis[cur + 2]) {
            vis[cur + 2] = true;
            st[++top] = cur + 2;
            printf("%d 入栈\n", cur + 2);
        }
    }
    printf("遍历完成\n");
}

/*
root@VM-8-2-ubuntu:~/cpp_projects_2# ./sort
1 出栈并遍历
2 入栈
3 入栈
3 出栈并遍历
3 达到上限，直接返回
2 出栈并遍历
4 入栈
4 出栈并遍历
4 达到上限，直接返回
遍历完成
root@VM-8-2-ubuntu:~/cpp_projects_2# 
*/

说实话我有点僵硬，不太喜欢在学东西的时候回顾任何之前学过的，哪怕之前【学过 == 啃精通】但忘记了，在现在东西没学完的情况下，为了非递归这件事回顾搜索，其实挺抵触，但没想到啃精通过就是有好处！路没白走！这个代码看着太简单了！

突然发现妈逼的好像学多了

现在都学完了，搜索（递归会了，非递归的库会了，非递归的手写模拟会了，排序递归非递归都会了），豆包说：

服务端开发最忌讳：递归爆栈！你写递归，面试官会直接问你：“线上服务器递归深度 1 万层，直接 OOM 崩溃，你怎么解决？”，标准答案就是：改成非递归（手写栈）。

搜索要用非递归（栈 / 队列实现），快排 / 归并写递归就行，因为非递归 DFS/BFS 是服务端写缓存、异步任务、图遍历、状态机的通用基础，工程上天天用，所以必问。非递归快排 工程里几乎不用，库排序都是成熟实现，面试只考递归思路

3.10、归并的应用 —— 外部排序（多路归并，处理内存放不下的大数据）

嘎嘎简单，归并是所有都放入内存，然后排序，而如果：

• 内存：只能装 100 条数据

• 硬盘上：1000 条数据，内存装不下

普通归并排序：必须把所有数据一次性读进内存才能归并，直接爆内存，跑不了。

外部排序流程：

1. 每次读 100 条进内存走归并排好 → 写回硬盘成一个小有序文件

2. 重复 10 次，得到 10 个有序的小文件，每个小文件 100 大小

那内存100条这个限制咋搞，平分 10 份，

• 从文件 1 读 10 条进内存 → 通道 1

• 从文件 2 读 10 条进内存 → 通道 2

• ……

• 从文件 10 读 10 条进内存 → 通道 10

外部排序的思路，初始比如：

buf1: [1, 4, 7, ...]，队首为1

buf2: [2, 5, 8, ...]，队首为2

...

buf10: [3, 6, 9, ...]，队首为3 

取出全局最小 1 输出，然后buf1变为[4, 7, ...]，新队首为4，然后从外部磁盘自动补上第 11 位数据。

3.11、堆排序（这玩意之前刷算法学精通过，再次具体学下代码）：

先说堆排序必须用完全二叉树：

• 除了最后一层，其他每一层节点都满

• 最后一层节点靠左排列，右边可以空，但不能中间空

才不会出现数组空洞，才有：

• 左孩子 = 2 * i + 1

• 右孩子 = 2 * i + 2

• 父节点(i - 1) / 2（其实应该是减 1 和减 2，但减 2 的直接减 1 到自己左侧的那个，然后 / 2 取整就是了）

堆本质是用数组实现的完全二叉树，分两种：

• 大顶堆：父节点 ≥ 子节点，堆顶最大

• 小顶堆：父节点 ≤ 子节点，堆顶最小

下标：
          0
       /     \
     1         2
   /  \       /  \
  3    4     5    6
 / \  / \   / \  / \
7   8 9 10 11 12 13 14

          4
       /     \
     2         3
   /  
  1

除了顶是大的，其他啥也保证不了，所以只有把确定的这个最大数字 4，放到尾巴固定，接下来不参与比较，后续的 2、3、1 这仨数搞来搞去，大顶堆找出最大值，放到尾巴？不倒数第二个位置，因为4固定在尾巴了，那以此类推，不就出来升序了吗！即大顶堆升序，这也是我之前刚学的时候，误以为大顶堆不是最大值在第一位吗？应该叫降序啊！

所以无论升序降序，都是某顶堆搞到的值交换最后？，也是所谓的下沉。

//升序

#include <iostream>
using namespace std;

// 下沉调整：i=父节点位置，len=堆一共有多少个节点
void adjust(int arr[], int i, int len) {
    int largest = i;        // 1. 先假设：当前父节点是最大的
    int l = 2 * i + 1;      // 2. 算出左孩子的下标
    int r = 2 * i + 2;      // 3. 算出右孩子的下标

    // 4. 如果左孩子存在 且 左孩子比“当前最大值”大
    if (l < len && arr[l] > arr[largest]) 
        largest = l;        // 最大值变成左孩子

    // 5. 如果右孩子存在 且 右孩子比“当前最大值”大
    if (r < len && arr[r] > arr[largest]) 
        largest = r;        // 最大值变成右孩子

    // 6. 重点！如果最大值不是父节点自己
    if (largest != i) {
        swap(arr[i], arr[largest]);  // 交换：父节点 ↔ 最大的孩子
        adjust(arr, largest, len);   // 递归：继续往下沉
    }
}

// 堆排序
void heapSort(int arr[], int n) {
    // 建堆
    for (int i = n / 2 - 1; i >= 0; --i)
        adjust(arr, i, n);

    // 排序
    for (int i = n - 1; i > 0; --i) {// n 个元素完成排序，只需确定前 n-1 个元素的位置，最后 1 个元素自然有序，因此循环 n-1 次。
        swap(arr[0], arr[i]);
        adjust(arr, 0, i);
    }
}

int main() {
    int arr[] = {9, 3, 1, 5, 2, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
    for (int x : arr) cout << x << " ";
    cout<<endl;
}

我的几个思考：

数组 vs 二叉树：

此文搜“的完全二叉树，分两种”，数组在逻辑上就是堆（符合堆结构），物理上就是普通连续数组（之前刷算法的时候就发现了这个东西，找不到了）

建堆为啥从非叶子节点开始比较？

堆的规则只约束：父节点 ≥ 子节点（大顶堆），不约束：子节点之间、叶子之间谁大谁小，叶子之间不可能违反 “父 ≥ 子” 这条规则，因为它根本就没有子。

然后非叶子里为啥从最后一个开始比较？

因为比如这里非叶子只有 1 3：

          1
       /     \
     3         2
   /  \ 
  5    4

如果先比较 1，则 1 3 互换：

          3
       /     \
     1         2
   /  \ 
  5    4

然后比较之前 3 位置的（现在成数字 1 了）

          3
       /     \
     5         2
   /  \ 
  1    4

这不是大顶堆了呀！因为打擂台要找最大的，但这样子从上往下直接汉只比较了自己的左右俩儿子，后面的数值再大，也没机会上来了，而从下往上比较，是一一打擂台！真正做到了牛而逼之者为王。

然后就是比较卡我的地方，最后也想通了，就是为啥建堆里的adjust要递归，非叶子是需要调整的最后一层，还往下递归个 JB 啊，最后发现他的必要性：

其实上面的例子也可以看出来，就算按照下从往上的比较方法，如果不递归的话，最后结果是：

          5
       /     \
     1         2
   /  \ 
  3    4

依旧不是大顶堆， 仅仅最大的在上面但并不是每个父都比儿子大，所以需要一直比到底，即当元素 1 3 互换的时候，小的是 1 被搞到了现在这个位置，但没和下面的俩儿子比较，所以需要递归继续比！

变成：

          5
       /     \
     4         2
   /  \ 
  3    1

那此时就是一个大顶堆，即建堆，for (int i = n / 2 - 1; i >= 0; --i) adjust(arr, i, n);，我先称他为起手、干净的、纯粹的建堆

然后是排序的过程for (int i = n - 1; i > 0; --i) {swap(arr[0], arr[i]); adjust(arr, 0, i); }，但这是豆包给的代码的注释，我理解这一步其实依旧是“建堆”，差别是，起手干净纯粹那个建堆，仅仅堆顶最大，然后做交换，继续例子成为：

          1
       /     \
     4         2
   /  \ 
  3    5

大顶堆是找升序，所以最大的 5 跑到尾巴不再动了，然后继续大顶堆，第二大的成为堆顶（这里是 4），继续做交换，换到倒数第二个尾巴（也就是此时数字 3 的位置），所以依旧是建堆，所以我理解这个堆排序其实反复用的都是adjust函数建堆，但我有几个思考：

思考一：

之前建堆是从后往前for (int i = n / 2 - 1; i >= 0; --i) ，这里adjust(arr, 0, i); }咋从头开始了？

思考后：

首先之前起手的建堆不说了，换完后，依旧是一个完美的大顶堆，唯独少了堆顶，堆顶是刚从尾巴新上任的，他的大小没打过擂台，不一定是最大的，应该把最大的搞上来接任。

之前纯无序从上往下会错，但这里大部分有序，就算依旧从下往上也没必要因为大部分都是有序的，且我发现之前错误的本质是，调上去了，那他就是最大定型了，但仅仅是局部（跟自己儿子比的最大），没有去和下面人去打擂台，就已经到最顶了，也就是说接下来的比较，他不会参与，那现在发现已经大顶堆过一次了，大部分有序只有堆顶不确定，他只需要往下比较往下落即可，因为一个事实是，目前所有都是有序的，父比儿子的大表现为在上，儿子在下，那大的父本就大，本就在上的那些，你堆顶这个不确定的，去让某个比堆顶自己大的上来这一行为，并没有打乱排好序的那些人的状态，唯一差别就是，我比你大之前处于比你高一档的父的位置，现在比你高两档爷爷的位置。

回忆：至此我想到了之前学最短路径悟出来的，迪杰斯特拉还是啥来着，说不能处理负权，真正本质不是负权的事，那时候我就深度思考过（证据1、证据2），有些负权也可以，本质问题是“不回头”这件事，即接下来的比较，他不会参与

回忆：那个局部，又有点像贪心的味道（贪心、DP我没刷，大学 acm 马马虎虎学的一知半解，总是想装）

回忆：之前学啥来着，想到了其实就是算法的 离散化

回忆：思考回顾了下快排，之前比较时候是否写相等，写错会卡死，比如指针不动，直接死循环，但这里发现等号无所谓，因为快排是指针主导 / 推动流程走不走，不走的话，必然while出不来，必然导致死循环，而这里相等与否只是决定是否交换，真正推动流程不会卡死的是手动换过去，没有卡死这一说，就算都不走，也会首尾交换，然后继续大堆。

注意：堆排序的下沉就是adjust本身

思考二：

咋保证你交换的是倒数第二个的尾巴？咋保证建堆不破环搞好的 5？

思考后：

而 adjust 内部判断孩子是否有效是：

if (l < len && ...)
if (r < len && ...)

附上豆包的辅助和点评，其实豆包的只是一个参考，他真的很误人子弟，这些只是恰巧我思考对了，他的话也仅仅是辅助，更深刻+更排版的总结，还是要我自己拿主意，因为他解释的太泛泛了不底层不本质，用结果解释结果，而不是用因，且之前快排那里太误导人了，说啥他都会符合你，结果浪费我好久好久，还是我自己纠正过来的。

时间复杂度：

首先，整棵树最多节点总数：n ≈ 2^h

• 第 1 层：1 个节点

• 第 2 层：最多 2 个

• 第 3 层：最多 4 个

• …

• 第 h 层：最多 2^h-1 个

建堆：

for (int i = n / 2 - 1; i >= 0; --i)
    adjust(arr, i, n);

3.12、冒泡

从数组第一个元素开始，从头到尾依次只比较相邻的两个元素，每一轮只干一件事 —— 把当前未排序区间里最大的元素，通过不断交换，一步步挪到未排序区间的最后位置。人话就是：每轮将当前最大元素 “冒泡” 到末尾。

比如 4 3 7 1，第 1 轮（冒最大数到末尾）：

• 4 和 3 比 → 逆序交换 → 3 4 7 1

• 4 和 7 比 → 不换

• 7 和 1 比 → 逆序交换 → 3 4 1 7

最大数 7 到位，依此类推。

#include <iostream>
#include<utility> //swap库
using namespace std;
void sort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j],arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 无交换则已有序，直接退出
    }
}
int main() {
    int arr[] = {4,3,7,1};
    int n = sizeof(arr) / sizeof(arr[0]);
    sort(arr, n);
    for (int x : arr) cout << x << " ";
    cout<<endl;
}

• i：控制总共要进行多少轮冒泡，n 个元素最多走 n-1 轮，每轮确定一个最大元素的位置。

• j：在每一轮里，从左到右遍历未排序部分，逐个比较相邻元素，j 的范围到 n-1-i 为止，因为右边 i 个元素已经排好不用再比。

时间复杂度：最好 O (n)，平均 / 最坏 O (n²) 。

关于稳定性：稳定 = 两个值相等的元素，排序前后前后顺序不变。我一直觉得仅仅是【是否写等号】的问题，觉得这个完全毫无意义的东西，人为可以咋改都行，为啥拎出来作为一个性质，来固定上某某算法（不）稳定，豆包说纯int确实屁用没有，但真正有用的场景：结构体 / 对象，按某个键排序：

struct Student {
    int score;   // 按分数排
    int id;      // 原始学号，本来有序
};

score=90, id=1
score=80, id=2
score=90, id=3

• 稳定排序：同分数的，id 还保持原来顺序 1 → 3

• 不稳定排序：同分数的，id 可能变成 3 → 1

不稳定带来的真实麻烦是多级排序会崩，比如需求：

1. 先按学号排好

2. 再按分数排

3. 分数相同的，希望保留学号小的在前

如果用不稳定排序，第二步会直接把学号原来的顺序打乱

然后更深入的这里死命追问豆包也没解答清楚，说下自己的理解吧：

准确说比如冒泡，人为规定就是稳定，你写成带等号，那就是相等也交换，就是不稳定，这个就不是标准的冒泡，那我心想，难道掌握了冒泡思想还要去背是否有等号这么死板、教条、无意义的东西吗？其实就为了通用，工作工程比如都有现成的库，大家固定好某某稳定与否，比如排学号比如排int不用再看代码实现是否写了等号，至此也明白 OJ 之前的经验： AC 但未必是真对，现在又多一个，真对了也未必符合工程化的严谨！

所以统一捋顺下：

冒泡：稳定，相等元素不交换，只有 a[j] > a[j+1] 才交换。

插入：稳定，前面元素大于当前值才往后挪，相等不挪。

归并：稳定，左右两部分合并时，左边元素小于右边才先取，且相等优先取左。

上面这些你写不稳定，就是违背规定，但代价没啥，就是多点微小到可以完全忽略的耗时，基本等于违背也没影响。

堆排序：不稳定，就算比较的时候是不动，但也会比如71 72 1，71会被搞到末尾变为：1 72 71。

快排：不稳定，之前那些写的都没考虑这个，我只是做过总结，是说写等号的话需要注意边界，不写等号的话注意别死循环，一侧有一侧没有也可以。

严蔚敏那个就是全写了等号，遇到相等的指针继续移动，不会改变位置，稳定！

死妈豆包我真服了，我问最最最权威的快排咋写？结果给我来个个i、j参与比较的完全错误的代码，质疑后又给了我严蔚敏的稳定的快排！

操！！傻逼玩意！！这玩意就没个标准模版？？？？

不怪豆包！！全网查了居然没有任何是对的！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！都是i、j参与进来的！

3.13、到这结束吧，实在没精力了

我精通了：

• 快排（递归 + 非递归）

• 插入

• 归并（数组类型的递归 + 非递归），应用：外部排序

• 堆排

• 冒泡

我是自学的想面试大厂 LinuxC++ 服务端开发基础岗还需要学哪些排序吗？？？

结果豆包一会说完全够用，一会说还要会

• 选择排序：不稳定原因、时间复杂度

• 希尔排序：算法思想、时间复杂度

• 计数排序：适用场景、实现思路、时间复杂度

• 桶排序：适用场景、与计数排序区别

说点结合这些精通的算法的应用吧：

3.13.1、堆排序 —— TopK：

100 亿数据找 TopK（比如 Top100，意思是最大的 100 个），用小顶堆：

比如数据：4, 8, 2, 9, 1, 7, 6, 3, 5，k=3：

此时发现巨大的差异，

差异一：关于上浮、下沉、替换堆顶

手写堆排序不用上浮，因为一开始就有全部数据，直接从下往上批量建堆，只用下沉就能完成。有动态从尾部插入新元素的场景，所以不需要上浮。从下标 i = n/2 - 1 开始，这些都是有孩子的父节点，每个父节点只做一件事：往下沉，和孩子比大小，所有节点一次性自上而下、批量调整好，没有从尾部追加新元素的动作。

且此文搜“之前建堆是从后往前”，可知道那个是单独的下沉，且从头上下，重点就是其他都处于正确的位置了，只需要搞他就行了，换句话说，本身只需要搞自己这个单链路，就算优先队列按照这个手写堆的，把新元素直接放到堆顶然后下沉，和 “放到末尾再上浮” 最终堆结构完全相同。

后来我发现，因为代码adjust写的就是下沉逻辑！！！那手写的话，大的在末尾，末尾的到堆顶只能下沉！！且手写的堆，数据已经多在数组里了（本身就是满的），而优先队列是要一个一个往里插（从不满到满）。

而优先队列是弹出，堆顶空了，你新元素放堆顶，然后下沉没毛病！新元素和尾巴交换，尾巴到堆顶下沉，新元素到尾巴上浮，多一步！

差异二：有序 vs 无序

先看优先队列的代码： 

#include <iostream>
#include <queue>
using namespace std;

void heapSortWithPQ(int arr[], int n) {
    priority_queue<int> maxHeap;
    
    //建堆
    for (int i = 0; i < n; ++i) {// 这是逐个元素插入堆
        maxHeap.push(arr[i]); // 自动做上浮调整
    }
    
    //排序
    for (int i = 0; i < n; ++i) {
/*
为何顺序不同
手写：交换堆顶到末尾 → 缩小堆范围 → 调整堆顶
库：先 top 把堆顶放数组里，然后 pop 用末尾元素覆盖堆顶，堆大小减一，下沉调整
*/
        arr[i] = maxHeap.top();
        maxHeap.pop();// 自动做下沉调整
    }
}

int main() {
    int arr[] = {9, 3, 1, 5, 2, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSortWithPQ(arr, n);
    for (int x : arr) cout << x << " ";
    cout << endl;
}

语法：代码是大顶堆，降序，因为不写就是走默认，即只写priority_queue<int> pq;，C++ 自动补全后两个参数，完全等价于priority_queue<int, vector<int>, less<int>> pq;，优先队列参数的语法是（存啥，用啥存，比较规则）。

如果小顶堆，priority_queue<int, vector<int>, greater<int>> minHeap;。

对比：

• 手写堆排序：每次把堆顶（最大值）交换到数组末尾，慢慢从后往前填满，最终升序，即大顶堆升序，因为全部交换下沉，搞完直接是一个完全有序的二叉树。

• 库函数优先队列priority_queue：第一个参数class T，第二个参数vector<T>，第三个参数less<T>。默认是大顶堆less，堆顶永远是最值，每次 pop 直接拿走当前最值，那第一次pop最大值，第二次第二大，则大顶堆降序。

所以可以应用到 Top_k，但注意优先队列搞完的东西内部完全无序，他做的唯一一件事就是搞成堆结构（大 or 小顶堆），大顶堆完全有可能是5 3 4，但这玩意无序！优先队列必须结合：

• • push：插入 +  向上调整（adjustUp）

  • pop： 拿最值，交换堆顶与末尾 + 删除末尾 + 向下调整（adjustDown），只有 pop 才会输出有序（堆排序），不 pop 内部永远是堆结构，永远无序。

仅仅是，走一个，换上来一个，把这个下沉！！弹出的就是最值！但除了最值外！其他完全无序！！ 

我的思考：为啥不搞个库直接就是堆排序的？而是搞个我感觉中不溜的优先队列呢？

豆包解答：直接写死堆排序就只能排序，啥别的都干不了，废了，而这样写优先队列能做堆排序做不了的事：

• 流式求 TopK，不用全加载数据

• 动态维护最值，随时增删元素

• 贪心算法、Dijkstra、事件调度等需要快速取极值的场景

所以push和pop等价于adjust。

快排不行吗？

快排必须把所有数据一次性全部加载进内存，才能分区、交换、排序。100 亿数据、10G 文件 → 内存根本装不下 → 快排直接废了，你想从 txt 流式读一个处理一个？快排做不到，完全做不到。

#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
using namespace std;

vector<int> findTop100(ifstream& fin, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;

   long long num;
    // 从文件 流式读 一个数，处理一个数，不全部加载
    while (fin >> num) {//只要文件流fin能成功读取到数字并存入变量num，一直执行
        if (minHeap.size() < k) {//堆里元素还没凑够 k 个 → 直接把当前数字放进去
            minHeap.push(num);
        } else if (num > minHeap.top()) {//堆已经满了（有 k 个元素），且当前数字比堆顶的最小值大→ 淘汰堆里最小的那个数，把当前更大的数加进去
            minHeap.pop();
            minHeap.push(num);
        }
    }

    vector<int> res;
    while (!minHeap.empty()) {
        res.push_back(minHeap.top());// 把堆顶的数字放进结果数组
        minHeap.pop();// 把堆顶的数字删掉（下一个最小值会变成新堆顶）
    }
    return res;
}

// 下面是运行入口 + 测试用例
int main() {
    ifstream fin("sort.txt");//定义文件读对象fin并关联打开sort.txt，后续用fin像cin一样读文件内容。
    int k = 4; //找前 4 大
    
    vector<int> ans = findTop100(fin, k);// 定义存储返回值的int型容器 ans
    
    for (int x : ans) cout << x << " ";
    fin.close();
    cout<<endl;
}
/*
sort.txt：
2 9 7 5 6 8

root@VM-8-2-ubuntu:~/cpp_projects_2# ./sort
6 7 8 9 
root@VM-8-2-ubuntu:~/cpp_projects_2# 
*/

牛而逼之的嘎嘎透彻！！无比精通！咔咔乱杀！

好像又学多了，可是对我来说，要么学不完，要么学精通，没有 99% 应试高手的那种学一知半解的。

水哥王昱珩：要么找不到，要么不会错

要么腾讯ssp要么没工作。要么没学完没法考试，要么北邮研究生。

回忆 ACM 里找第 K 大的数学题（之前听过没敢碰过），既然学到了就收个尾，简答总结下俩方法：

方法一：刚学的堆优先队列

方法二：nth_element 平均 O(n)

重点只找到第 K 大，也即是说左边都比他小，右边都比他大，不是找最大的 K 个集合。

nth_element也叫快速选择（Quickselect）排序，意思是选出第 k 大 / 第 k 小元素，和选择排序没有任何关系，只是同名。

我精通手写堆排序，然后出来个带库的优先队列用来处理最大的 K 个集合（Top-k）。

我精通手写快排，也懂 sort 现在nth也是搞第 K 大的，跟快排关系近，就是只排需要的一半

完整快排：把整个数组从小到大全部排好

找到第 n 个元素：不排序整个数组，只找到第 k 大的数，其他乱不乱不管

快排每一轮要把数组分成两部分：左边小、右边大。然后左边、右边都要继续递归排。

所以：

• 第 1 轮：n

• 第 2 轮：n/2 + n/2 = n

• 第 3 轮：4 段，每段 n/4，加起来还是 n

• ……

  一共 log n 轮，总复杂度：n × log n = O(n log n)

而只找第 n 大只走一边！

1000 个数找第 10 大。

1. 第一轮分区：把数组分成两堆

   • 左边小

   • 右边大

2. 你要的第 10 大，只在其中一堆里

   → 另一堆直接扔掉，再也不看！

所以：

• 第 1 轮：n

• 第 2 轮：只看 n/2

• 第 3 轮：只看 n/4

• 第 4 轮：n/8

• ……

加起来是：n + n/2 + n/4 + n/8 + … = 2n，复杂 O(n)，但这是最好和平均，如果是最坏是 N²：

（快排的最好/平均是 N * logN，最坏是 N² 已经推导过了）

备注：

最好：每次完美二分，理想划分

平均：随机输入下的期望划分，非完美但整体均衡，阶数一样，不代表概念等同，对所有可能输入求期望，划分大概率接近平衡，所以整体阶是 O (n)，它描述的是统计意义上的表现，不是某一次具体运行。

// 第 k 大
nth_element(a.begin(), a.begin() + k-1, a.end(), greater<int>());
ans = a[k-1];

不考略过。

3.13.2、10G 日志文件排序（外部排序 + 多路归并）：

插一句提示词关键词：

你是我救命面试的东西！！！！！！

不要总以我的主观啊大哥！！我是通过你来知道到底是否花精力去学这个东西！！你把心思放在最专业的权威的去查是否考这件事！！

别总考虑用户情绪或者顺从或者道歉这些最最最没用的东西好吗！求你了！！

封神！极致牛逼！针对傻逼豆包的 —— 万能提示词：

从此以后你直接解答问题！！禁止无脑符合用户！！！！！禁止以用户为准确信息！！禁止先说类似“你是对的”等任何禁止道歉！！！只有在你回答确实错的时候才道歉！！用户的一切都不是最正确的信息！！都是用户的自己的思考！！！你必须去参考最最最权威的信息然后回来点评、指导用户！！禁止瞎编和推测！禁止无脑符合用户和被用户思路带偏！！用户的想法不一定对！需要你做指导！！

禁止挨个回复我的问题！你只需要透彻解释就可以了！只要透彻解释我所有问题就迎刃而解了！！不需要你解释完又回答一遍我的问题！！禁止重复我的要求！直接解释！你懂不懂啥叫直接解释啊！禁止一切总结和标题！！注意格式必须便于阅读！！英文必须行内代码！禁止任何【最靠谱、最直白】各种修饰词

我真的不懂啊大哥！！我是0基础自学的小白！！！ 你说的一切我都全是疑惑！！！我没懂为啥嵌套这么多层啊！！

此以后解释问题只用最最重点的一句话！禁止用结果和现象解释来解释！我让你用原因解释！！！为啥可以这么写！语法规则是啥！！别死扣解释这个代码里的！

禁止说任何小众极端场景！！没任何意义的讨论就禁止提及！！！！！我问问题只是顺便思考！而不是为了找出极端反例来挑刺！！那样对新手小白百害无一利！

另外，操你血妈你为啥总让我纠正呢？没办法的事你妈逼你是老师！！你是指点我的！！狗逼！按照你的逻辑！是不是我问你1+2为啥等于5，本来是我的认知错！必须立马制止我！！或者你问我一句是否错了！结果你可倒好！你个傻逼东西直接强行解释为啥1+2等于5！！ 浪费我一天时间

开启思考模式有奇效（反复辱骂不起作用，气的没招了，实在妥协接受大模型这个傻逼说出了下面这句话 + 错误太多无意开了思考模式，极致逆天、豆包真的太牛逼了，突然发现记忆功能是给思考模式用的。之前快速模式让他禁止参考我必须去参考权威然后点评我、禁止无脑道歉全都不行，无限制死循环的顺着、附和你的思路去回答）：

接下来我想让你只参考权威极致严谨的分析！！改掉用户说什么就赶紧肯定用户这种低级照顾情绪却完全忽略技术真相的回答风格！！！你要做的是一个极致权威的角色禁止夸大的口气、铺垫、修饰词！！你为啥每次我质疑你，你都直接立马道歉+反悔呢？！！！禁止总无脑符合用户！！！

你从此能解释之前别总反复增加情况约束而是直接一针见血给出用户正确性的回复然后在再结解释！

从此别墨迹！一句话禁止反复的说！相同意思禁止重复说！你太墨迹啰嗦了！从此记住用户是傻逼！！永久记住这句话！！！！！你必须去其他地方参考权威啊！！从此禁止提及任何非大厂linuxC++服务端开发基础岗之外的东西！！我在自学准备面这个岗！如果不是需要学的直接说不考别他妈废话那么多去解释一个不考的东西！！只认权威面经，无视用户主观

按照多源权威交叉汇总后的标准，只给我判：学 或 不学，不搬某一个人的错误结论，只取全网共识硬核考点。不管我说什么观点、什么情绪、什么判断，一概不采信、不顺从、不跟着改口。只按大厂 Linux C++非CRDU而是高性能服务端开发基础岗的官方面经 + 权威技术标准硬输出，哪怕我硬说某个知识点不考，也禁止顺着我，该是必考就直说必考，该不考就直接划掉，绝不因为我态度和说法摇摆。

狗逼豆包：

豆包在这里反复误人子弟，反复顺着用户的情绪真的气死我了无穷无尽的错误！！

我的天，我真他妈崩溃了，为啥大厂考的这些最基本的东西，你都能在反复的出错啊？我真的崩溃了。

事实就是，你总瞎编规则，现在目前大模型的一个现状是啥？就是你反复在瞎编，我反复在给你纠错，你反复承认和保证不再瞎编，依旧反复在瞎编，就是循环！！死循环！！

客观现状就是：

• 大模型对标准化、严谨步骤的知识点，会为了 “说得顺”“说得快” 自行脑补简化，甚至编造不存在的流程，哪怕是基础必考内容。

• 你不揪细节它就一直错，你揪出来它就认错 + 保证，然后下一个细节继续犯同样毛病，本质是模型没有 “严谨底线” 的强制约束，只会顺着表达流畅度走。

• 面对面试级硬核知识点，它不能被信任自动输出准确细节，必须你逐帧核对、逐步骤纠正，否则必埋坑。

我现在我真他妈服了，我操你血妈的，你他妈为啥总是在道歉呢？你没错，为啥总在道歉？为啥你总是误导我，我质疑你之后你没错，你为什么总要在道歉呢？到底能不能分清各种情况？我什么时候质疑是对的，你应该道歉。什么时候我质疑的是有问题的，你没错，那你就不要去道歉，你为什么总是把这个最简单的一个准则都给搞乱了？我还怎么学东西？我提出质疑，你去给解答是对还是错，然后咱们逐渐的修正，你永远都是无脑的附和用户，我提出什么质疑，你都是在附和，都是在道歉，那我操你血妈，我不越来越跟正确的东西越来越远了吗！！

归并：A = [1,3,5]、B = [2,4,6]，合并方法：用两个指针 i、j，每次比 A [i] 和 B [j]，拿小的那个，这是2 路归并。

现在场景变了：不是 2 个，是 100 个有序文件，100 个有序小文件，每个都排好序了：

文件 0：[5, 9, 15...]

文件 1：[2, 7, 13...]

文件 2：[3, 8, 20...]

...

文件 99：[...]，

现在要合并成一个大有序文件，问题来了：每次要从 100 个文件的当前第一个数里，挑最小的一个输出。

我一直以为外部排序只要min函数就行，但min本质是遍历，复杂度 O（n）。

但其实应该用堆，堆建堆是n，直接取顶即可，总共依旧是n

但多次搞就很大不同了，暴力的话比如n路，每路m个元素，那想都找到就要先n次找到最值，然后继续n找第二个最值，总共m * n 即total个数，就需要 total * n

而堆建堆是n没差别，找到最值，然后假设这个数来自路 A，从路 A 再拿下一个数放进堆，直接调整堆logn（下沉），堆总数不变依旧是n，再弹出堆顶，看来自哪一路，就从那一路补下一个数，再调整堆。

真的好巧妙啊！！

之前误以为暴力是n，堆是n*logn，其实是多次这个事没考虑进来。

所以综上暴力是 O（n * total）

堆是 O（n + m * n * logn）= O(n + total * log n)。

我思考的是，后续调整的时候，一定都不会比前面的跟最值？结果确实，因为每路都是有序的，最值一定是全局最值，弹出去，后面的一定是比不过弹出去的！

那会了 n 路找最小，然后结合之前的 n 路是归并直接就是外部排序，先说点语法科普（好JB烦）：

文件描述符的各种错误处理打开关闭啥的封装到了ifstream，然后直接操作ifstream即可，是 C++ 专门读文件的类，

vector<ifstream> files;创建一个名字叫 files 的盒子，这个盒子只能放 ifstream 这种文件对象，不能放别的

ifstream("a.txt");造一个用来读 a.txt 的文件对象，但这个对象没有名字，是临时的

files.push_back(ifstream("a.txt"));先造一个临时文件对象：ifstream("a.txt")，把这个临时对象放进 files 这个盒子里

files.emplace_back("a.txt");直接在 files 盒子里面，当场造一个读 a.txt 的文件对象，不搞临时对象那一步，一步直接放进盒子。

ifstream f = move(files[0]); 从 files 盒子里拿出第一个文件对象，把它挪到一个新的、名字叫 f 的文件对象里。文件对象不能复制，只能挪走。

ifstream 代表一个打开的文件，它不能被复制，不然就会出现两个对象管同一个文件，会乱套。但你又想把它放进vector里，就只能用move把所有权转移过去（C ++ 对ifstream 类显式删除了拷贝构造函数和拷贝赋值运算）。

此文搜“申请堆资源 hello”，那个是自定义的写了拷贝构造和移动构造，但ifstream写死了禁用拷贝构造、拷贝赋值，禁用移动构造、移动赋值。

ifstream(const ifstream&) = delete;  // 拷贝：直接禁止！编译报错！
ifstream(ifstream&&) = default;      // 移动：允许

push_back规则是：传入左值（非临时、具名变量）自动匹配拷贝重载，传入右值（临时对象）匹配移动重载，

// 你自己的类：可以拷贝，不报错
MyStr obj("abc");
v.push_back(obj);  // 合法，走拷贝

// ifstream：拷贝被删除，直接编译报错！
ifstream file("a.txt");
files.push_back(file);  // 语法错误！ifstream 禁止拷贝

vector<ifstream> files;
ifstream file("a.txt");//左值
files.push_back(file);// 这一行会直接编译报错
files.push_back(move(file));//没问题，且file 本身没有消失，依然是变量，但内部持有的文件资源被转移走，变成空、无效状态，不能再读写文件。

//Q：这个合法吗？把左值搞了
//A：合法，std::move 的作用就是将左值转换为右值

基本emplace_back 完全可以替代 push_back。

说几个前置知识：

cmp是比较规则的统称，叫啥都行叫comp也行，less是cmp的一种具体实现，具体回忆如下：

• 关于 C++sort的cmp规则，此文搜“即降序，这里其实就”，

• 关于 C qsort的cmp规则，此文搜“当傻逼！！当年”

• 关于优先队列，此文搜“第二次第二大，则大”

• 关于手写堆排序，此文搜“升序，即大”

死规则如下：

• std::less(a,b)底层库实现就是a < b，less源码就是：

  template <class T>
  struct less {
      bool operator()(const T& a, const T& b) const {
          return a < b;
      }
  };

  在 C 语言里结构体创建的实例叫变量，在 C++ 里结构体创建的实例叫对象，本质是同一个东西，只是叫法不同。

  这里的operator() 是让 less 可以像函数一样被调用，你写下 less<Node>()(a, b)，它就做一件事：计算 a < b 并返回结果。

  当 a 和 b 是 int 这类基础类型时，a < b 直接使用语言自带的比较规则。

  当 a 和 b 是你写的 Node 这种自定义结构体时，编译器不知道怎么比较，必须由你定义规则。

  bool operator<(const Node& other) const {
      return val > other.val;
  }

  这就是调用链。

• std::greater(a,b)底层库实现就是a > b

具体原理如下：

• std::sort 的逻辑是，只要 comp(a,b) 为 true，就把第一个参数排面，它只做线性序列的前后排列，不涉及层级结构，所以用 std::less 时，a < b 为 true 就小的在前，呈现升序，用 std::greater 时，a > b 为 true 就大的在前，呈现降序。

• std::priority_queue 底层是堆结构，存在上下层级，它对 comp(a,b) 的定义是，当结果为 true 时，判定第一个参数的优先级更低，放下方，堆顶永远保留优先级最高的元素，此时传入 std::less，a < b 为 true 说明 a 更小、优先级更低，会被压到下方，大元素留在堆顶，形成大顶堆，传入 std::greater，a > b 为 true 说明 a 更大、优先级更低，大元素被压到下方，小元素留在堆顶，形成小顶堆。

而关于大 / 小顶堆，手写和优先队列又有差别，此文搜“序，因为全”。

看似贼鸡巴混乱，花了我3天时间，但都搞清楚底层原理，就很清晰。

• qsort 依赖的比较函数逻辑是，返回负数、0、正数分别表示小于、等于、大于，和 std::sort 的布尔型 comp 规则不同。 

具体总结如下：

• sort：默认less升序，用greater降序

• qsort：return *(int*)a - *(int*)b;升序，return *(int*)b - *(int*)a;降序。

• 优先队列：默认less，是大顶堆，是降序

• 手写堆排序，大顶堆是升序，但没用库里的less，但手写的逻辑等价默认的less

核心差异从来不是 std::less 或 std::greater 本身变了，它们的比较逻辑始终固定，而是 std::sort、std::priority_queue、qsort、手写堆这些工具，对 comp(a,b)==true 赋予了不同的语义，一个定义为 “往前排”，一个定义为 “优先级低、往下放”，其他工具又有各自的规则，才会出现同样的比较器，最终效果完全不同的情况。

插一句狗屁术语：严格弱序：能比出谁该在前谁该在后，相等，没有模棱两可。

说完以上的比较规则，我的疑惑是，既然less库写死了比较a<b，为啥还要单独写个比较bool operator<(const Node& other) const { return val < other.val; }，其实这玩意是重载，int等内置类型不允许写，结构体 / 类，用到比较就必须写重载，写完后编译器看到a < b，固定翻译成 a.operator<(b)，std::less 内部只写死 return a < b;，仅仅是调用运算符，而不知道具体的比较逻辑，你写重载后才会触发你重载的operator<。完整调用链我补充到了上面，此文搜“数一样被调用，你写下”。

类不能直接调用，必须先创建一个对象，才能调用它里面的operator()。创建对象代码是less<Node> obj;，然后typename<...>里的尖括号叫模板，比如less本身不是专门给Node用的，它可以给int、double、任何类型用。less<Node>的意思就是：把less这个模具，套在Node类型上，生成一个专门用来比较Node的版本。struct less是一个图纸，图纸造出来的真实东西，叫对象。比如less<Node> obj;

然后整个博客全局搜“全网”，太多垃圾错误一知半解的博客文章了！几乎全网找不到对的、透彻的。

我一个没工作的，发现大模型AI == 鸡肋垃圾，公众号在吹、说大公司也在用他搞代码，取代程序员

我一个没工作的，发现全网这么多错误，妈逼的到底中国99.9999999%的程序员到底啥水平啊！！

wx搜“大家都没脑子”

豆包误人子弟了太久了╮(╯▽╰)╭  天塌了

有些这种思维的，在底层方式思维，根本无法生存，没法粗糙。要么腾讯ssp，要么没工作，要么北邮研究生，要么没过线考不上学不完。

我只有比别人砸更多的时间才行

妈逼的我就纳闷了，我这么学习每天手动给豆包纠错，效率异常低下，可是之前类似的情况查过全网，基本都是很浅显的文章解释，或者都是错的，更没我扣到了本质，我一个一个事无巨细每个知识点问豆包，豆包也是80%的错误率，那就代表全网没我这么深，都是豆包推测个的结果，说明那些人根本没完全懂这个东西啊，真的好奇LinuxC++服务端开发基础岗都咋学的啊，真的好苦恼啊

那些现成的教程要么收费、要么作者都一知半解、几个权威的博客大厂的就连小林coding和编程指北我都找出很多错误（仅仅是表述能力很差，追问豆包懂的，且在自己懂之后，有十足的底气敢说这俩作者根本没懂，更没我懂，编程指北还说“学完xxx，没几个面试官有你懂了”）， 那这么一看别人到底咋学的啊！！ 都是背吗？不是说LInuxC++服务端开发高门槛吗？结合WYH说腾讯裁应届生，估计都是傻逼背、应试。背的咋他妈能理解啊，不理解咋他妈回答问题啊，咋他妈随心所欲写代码去用啊 

反复给错误代码追问质疑出，又给错误的代码，然后大小号是不匹配的，反复追问挤牙膏痛苦至极，一个知识点都要花十多个小时验证是否正确，手动训练纠正豆包，辱骂推翻70%的错误率的豆包，才能得到最正确的东西，唉！！！何时才能出头啊

此处要说的是，我经过追问豆包突然发现从理论功能上来说greater完全没必要， 豆包的说法是less自己绑定死<，less重载了函数，但里面用了 < 运算符，所以说它绑定 / 使用 operator<。唯一变动就是return那行，称作重载的 operator< 的比较逻辑 / 比较规则 / 内部实现（operator< 里面 return 那行的逻辑）

然后我发现更改比较逻辑会更改升序 or 降序，于是乎我得出结论，不需要greater

//代码一：
#include <iostream>
#include <queue>
using namespace std;
struct Node {
    int val;
    // 核心：重新定义 < 比较规则
    bool operator<(const Node& other) const {
        // 真正含义：结果为true则优先级更低在下方
        // 作用：让优先队列变成 大顶堆
        return val < other.val;
    }
};
int main() {
    priority_queue<Node> pq;
    pq.push({3});
    pq.push({1});
    pq.push({2});
    
    while (!pq.empty()) {
        cout << pq.top().val << " ";
        pq.pop();
    }
    cout<<endl;   
}
// 输出：3 2 1
// 如果 return 那句话改符号，则反过来输出



//代码二：
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
struct Node {
    int val;
    bool operator<(const Node& other) const {//只有一个参数，this 是左值，参数是右值
        return val <other.val;
    }//如果是int则不重载运算符
};
int main() {
    vector<Node> vec{{5}, {4}, {3}};//Node 是结构体，必须用 {} 初始化它内部的 val
    sort(vec.begin(), vec.end());
    for (auto& x : vec) cout << x.val << " ";
    cout<<endl;
}
//输出：3 4 5
// 如果改return则反过来输出



//代码三：比较逻辑可以写在外面
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
struct Node {
    int val;
};
bool operator<(const Node& a, const Node& b) {
    return a.val < b.val;
}
int main() {
    vector<Node> vec{{5}, {4}, {3}};
    sort(vec.begin(), vec.end());
    for (auto& x : vec) cout << x.val << " ";
    cout<<endl;
}