C++中使用std::sort自定义排序规则时要注意的崩溃问题

ゝ一世哀愁。 2022-09-03 15:18 242阅读 0赞

### 文章目录 ###

*  前言
 *  sort的使用
 *  自定义比较函数
 *  sort源码崩溃分析
 *  为什么使用无保护的插入排序
 *  C++标准要求
 *  构造一个崩溃的示例
 *  平台差异
 *  总结

# 前言 #

看到这个标题应该会有很多人一下子就懂了，也会有些人感到迷惑，简简单单排序怎么会奔溃呢？我第一次接触这个问题还是很久以前刚刚参加工作的时候，当时也是写出了导致程序崩溃的代码，通过上网查询解决了问题，至此以后就对这个 `sort` 函数警惕了一些，一直记得就是在sort的自定义函数中判断条件不要加等号，至于本质的原因一直没有去探究，正好最近又改了一个相关的问题，所以决定从源码和定义的角度来看看为什么会出现这个问题。

# sort的使用 #

sort函数真的挺好用，比如像下面这样：

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    int main()
    { 
        std::vector<int> values{ 3, 5, 4, 4, 5, 1};
        std::sort(values.begin(), values.end());
    
        for (auto v : values) std::cout << v << std::endl;
    
        return 0;
    }

只是 `std::sort(values.begin(), values.end());` 这样简简单单的一句就完成了vector数据从小到达的排序，运行结果如下：

albert@home-pc:/data/cpp$ g++ testsort.cpp --std=c++11
    albert@home-pc:/data/cpp$ ./a.out
    1
    3
    4
    4
    5
    5

# 自定义比较函数 #

上面举的例子是从小到大排序，这是 sort 函数的默认行为，所以不需要额外的参数，如果是想从大到小排序，那么就需要定义一个比较函数了，方法也比较简单，写一个lambda表达式就可以了，比如像下面这样：

int main()
    { 
        std::vector<int> values{ 3, 5, 4, 4, 5, 1};
        std::sort(values.begin(), values.end(), [](int v1, int v2){ 
            return v1 >= v2;
        });
    
        for (auto v : values) std::cout << v << std::endl;
    
        return 0;
    }

按照比较函数定义，我们把数据按照前面大于等于后面的方式排序就完成了从大到小的排序的要求，看看这样写有没有什么问题？如果这里的等号 `=` 已经引起了你的不适，说明你可能踩过这里的坑，是的，这样写容易造成崩溃，我们来运行一下。

albert@home-pc:/data/cpp$ g++ testsort.cpp --std=c++11
    albert@home-pc:/data/cpp$ ./a.out
    5
    5
    4
    4
    3
    1

咦？怎么没事，我之前用MSVC测试还会崩溃的，难道和编译器有关？

当我们增大数据量

std::vector<int> values{ 3,5,4,4,1,5,4,5,4,5,4,5,4,5,4,5,4,4,5,4,4,4,5,4,5,5,4,5,4,4,5,4,5,4,5,5,5};
    
    // 运行结果如下
    
    
    albert@home-pc:/data/cpp$ g++ testsort.cpp --std=c++11 -g
    albert@home-pc:/data/cpp$ ./a.out
    0
    5
    5
    5
    5
    5
    5
    5
    5
    5
    5
    5
    5
    5
    5
    5
    5
    4
    4
    4
    4
    4
    4
    4
    4
    4
    4
    4
    4
    4
    4
    4
    4
    4
    4
    3
    1
    *** Error in `./a.out': double free or corruption (out): 0x0000000002016c20 ***
    ======= Backtrace: =========
    /lib/x86_64-linux-gnu/libc.so.6(+0x777f5)[0x7ff5ffef77f5]
    /lib/x86_64-linux-gnu/libc.so.6(+0x8038a)[0x7ff5fff0038a]
    /lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7ff5fff0458c]
    ./a.out[0x4024e2]
    ./a.out[0x4023ab]
    ./a.out[0x402226]
    ./a.out[0x4020a1]
    ./a.out[0x401edb]
    ./a.out[0x400c67]
    /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7ff5ffea0840]
    ./a.out[0x400a39]
    ======= Memory map: ========
    00400000-00403000 r-xp 00000000 00:00 212044                     /mnt/d/data/cpp/testsort/a.out
    00403000-00404000 r-xp 00003000 00:00 212044                     /mnt/d/data/cpp/testsort/a.out
    00603000-00604000 r--p 00003000 00:00 212044                     /mnt/d/data/cpp/testsort/a.out
    00604000-00605000 rw-p 00004000 00:00 212044                     /mnt/d/data/cpp/testsort/a.out
    02005000-02037000 rw-p 00000000 00:00 0                          [heap]
    7ff5f8000000-7ff5f8021000 rw-p 00000000 00:00 0
    7ff5f8021000-7ff5fc000000 ---p 00000000 00:00 0
    7ff5ffb70000-7ff5ffc78000 r-xp 00000000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
    7ff5ffc78000-7ff5ffc7a000 ---p 00108000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
    7ff5ffc7a000-7ff5ffe77000 ---p 0010a000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
    7ff5ffe77000-7ff5ffe78000 r--p 00107000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
    7ff5ffe78000-7ff5ffe79000 rw-p 00108000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
    7ff5ffe80000-7ff600040000 r-xp 00000000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
    7ff600040000-7ff600049000 ---p 001c0000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
    7ff600049000-7ff600240000 ---p 001c9000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
    7ff600240000-7ff600244000 r--p 001c0000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
    7ff600244000-7ff600246000 rw-p 001c4000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
    7ff600246000-7ff60024a000 rw-p 00000000 00:00 0
    7ff600250000-7ff600266000 r-xp 00000000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
    7ff600266000-7ff600465000 ---p 00016000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
    7ff600465000-7ff600466000 rw-p 00015000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
    7ff600470000-7ff6005e2000 r-xp 00000000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
    7ff6005e2000-7ff6005ef000 ---p 00172000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
    7ff6005ef000-7ff6007e2000 ---p 0017f000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
    7ff6007e2000-7ff6007ec000 r--p 00172000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
    7ff6007ec000-7ff6007ee000 rw-p 0017c000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
    7ff6007ee000-7ff6007f2000 rw-p 00000000 00:00 0
    7ff600800000-7ff600825000 r-xp 00000000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
    7ff600825000-7ff600826000 r-xp 00025000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
    7ff600a25000-7ff600a26000 r--p 00025000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
    7ff600a26000-7ff600a27000 rw-p 00026000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
    7ff600a27000-7ff600a28000 rw-p 00000000 00:00 0
    7ff600b70000-7ff600b71000 rw-p 00000000 00:00 0
    7ff600b80000-7ff600b82000 rw-p 00000000 00:00 0
    7ff600b90000-7ff600b91000 rw-p 00000000 00:00 0
    7ff600ba0000-7ff600ba1000 rw-p 00000000 00:00 0
    7ff600bb0000-7ff600bb1000 rw-p 00000000 00:00 0
    7ff600bc0000-7ff600bc1000 rw-p 00000000 00:00 0
    7fffc026e000-7fffc0a6e000 rw-p 00000000 00:00 0                  [stack]
    7fffc10b8000-7fffc10b9000 r-xp 00000000 00:00 0                  [vdso]
    Aborted (core dumped)

这次终于崩溃了，但显示确实内存越界问题，并且排序后第一个元素是0，这不是我们vector中的元素啊，看来肯定是出问题了

反复尝试几次又找到一个测试用例：

std::vector<int>values{ 3,5,4,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5};

运行之后直接得到了 `Segmentation fault (core dumped)` 错误，没错，这就是我想要的，来从 `sort` 源码中看看为什么加了 `=` 就会出现崩溃

# sort源码崩溃分析 #

sort 函数的源码还不算太长，我就一点点来看了

template<typename _RandomAccessIterator, typename _Compare>
        inline void
        sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
         _Compare __comp)
        { 
          // concept requirements
          __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
          __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_RandomAccessIterator>::value_type,
            typename iterator_traits<_RandomAccessIterator>::value_type>)
          __glibcxx_requires_valid_range(__first, __last);
    
          std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));

这算是个入口函数，做了一些类型检查，然后就调用了内部的 `std::__sort` 函数

template<typename _RandomAccessIterator, typename _Compare>
        inline void
        __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _Compare __comp)
        { 
          if (__first != __last)
          { 
            std::__introsort_loop(__first, __last,
                    std::__lg(__last - __first) * 2,
                    __comp);
            std::__final_insertion_sort(__first, __last, __comp);
          }
        }

当排序范围不为空时，函数会对传入的范围进行排序，为了最大程度的提高效率，结合了快排、堆排和插入排序等多种排序方法，分为 `std::__introsort_loop` 和 `std::__final_insertion_sort` 两个阶段。

第一阶段使用“快排+堆排”的方法，当元素个数小于等于 `_S_threshold`（`enum { _S_threshold = 16 }`）时，不做处理，交给第二阶段来做，对于元素个数大于\_S\_threshold的序列，执行快排，当快排的递归深入到一定深度 `__depth_limit`（通过元素个数计算出来的）时，不再递归深入，对待排序元素执行堆排序，代码如下：

/// This is a helper function for the sort routine.
      template<typename _RandomAccessIterator, typename _Size, typename _Compare>
        void
        __introsort_loop(_RandomAccessIterator __first,
                 _RandomAccessIterator __last,
                 _Size __depth_limit, _Compare __comp)
        { 
          while (__last - __first > int(_S_threshold))
          { 
            if (__depth_limit == 0)
            { 
              std::__partial_sort(__first, __last, __last, __comp);
              return;
            }
            --__depth_limit;
            _RandomAccessIterator __cut =
              std::__unguarded_partition_pivot(__first, __last, __comp);
            std::__introsort_loop(__cut, __last, __depth_limit, __comp);
            __last = __cut;
          }
        }

第二阶段使用“插入排序”，当元素个数小于等于 `_S_threshold`（`enum { _S_threshold = 16 }`）时，执行普通的插入排序，当大于 `_S_threshold` 时，执行两次的“插入”排序操作，首先使用普通的插入排序来排 `[first, _S_threshold)` 这个范围的元素，然后使用无保护的插入排序，完成 `[_S_threshold, last)` 这个范围的排序。

template<typename _RandomAccessIterator, typename _Compare>
        void
        __final_insertion_sort(_RandomAccessIterator __first,
                   _RandomAccessIterator __last, _Compare __comp)
        { 
          if (__last - __first > int(_S_threshold))
          { 
            std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
            std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
                            __comp);
          }
          else
            std::__insertion_sort(__first, __last, __comp);
        }

其中的普通插入排序没有什么特别的地方，就是遍历前边小于等于`_S_threshold`个元素进行普通的插入排序，而后面这个无保护的插入排序 `std::__unguarded_insertion_sort` 往往就是出现问题的地方，代码如下：

template<typename _RandomAccessIterator, typename _Compare>
        inline void
        __unguarded_insertion_sort(_RandomAccessIterator __first,
                       _RandomAccessIterator __last, _Compare __comp)
        { 
          for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
        std::__unguarded_linear_insert(__i,
                    __gnu_cxx::__ops::__val_comp_iter(__comp));
        }
    
      template<typename _RandomAccessIterator, typename _Compare>
        void
        __unguarded_linear_insert(_RandomAccessIterator __last,
                      _Compare __comp)
        { 
          typename iterator_traits<_RandomAccessIterator>::value_type
          __val = _GLIBCXX_MOVE(*__last);
          _RandomAccessIterator __next = __last;
          --__next;
          while (__comp(__val, __next))
          { 
            *__last = _GLIBCXX_MOVE(*__next);
            __last = __next;
            --__next;
          }
          *__last = _GLIBCXX_MOVE(__val);
        }

这段代码看 `__unguarded_insertion_sort` 还没有什么问题，但是 `__unguarded_linear_insert` 中的逻辑就比较迷幻了，只有当 `__comp(__val, __next)` 的值为false时才会停止。

其中 `__comp` 就是我们之前自定义的lambda表达式，我们当时写的是 `return v1 >= v2;`，翻译过来也就是当`!(val >= __next)` 时，即后一个元素小于前一个元素的时候停止，那么为什么会出问题呢？

我们知道前`_S_threshold`个元素我们之前已经按照从大到小排好序了，那么按道理遍历到这个区域就会找到后一个元素小于前一个元素的情况，也就是插入排序遍历到这就会停止，等等！好像有什么不对劲，如果这里的元素都相等就找不到停止的情况了，这就会造成访问的越界，这就是程序崩溃的本质原因了。

那么去掉等号会是个什么情况呢？运行到这里就是要找到满足条件的 `!(val > __next)`元素时停止，也就是找到后一个元素**小于等于**前一个元素的时候停止，因为前`_S_threshold`个元素已经排好序，这个条件是肯定满足的，所以不会出现越界情况，这就是为什么自定义比较函数中，两个元素相等时一定要返回false了。

# 为什么使用无保护的插入排序 #

既然这里这么容易越界，为什么不判断一下边界条件来防止越界，而是用这种无保护的插入排序呢？

这里使用无保护的插入排序原因很简单，就是为了提升效率，因为省略掉越界的检查，少了很多次的比较操作，效率肯定有了提升，它的前提是左边必须有已经排好序的元素，所以在函数 `__unguarded_insertion_sort` 函数之前先调用 `__insertion_sort` 来完成了`[0, _S_threshold)` 这个范围的元素排序，便是为了后面这个无保护插入排序的使用。

# C++标准要求 #

说到这里sort函数的自定义比较函数还是太容易出错了，有没有什么实现标准呢？其实标准中对这个比较函数的要求写的很详细，具体可以参考 [Compare的实现要求][Compare]。

**Compare** 是一些标准库函数针对用户提供的函数对象类型所期待的一组要求，其实就是要满足严格若排序关系，翻译成人话就是自定义的比较函数 `comp` 需要下面三条要求：

1.  对于任意元素a，需满足 `comp(a, a) == true`
2.  对于任意两个元素a和b，若 `comp(a, b)==true` 则要满足 `comp(b, a)==false`
3.  对于任意三个元素a、b和c，`若 comp(a, b)==true` 且 `comp(b, c)==true` 则需要满足 `comp(a, c)==true`

从这条规则也能看出我们之前定义的问题：

std::sort(values.begin(), values.end(), [](int v1, int v2){ 
            return v1 >= v2;
        });

这个自定义的比较函数，当 v1 和 v2 相等时，`comp(v1, v2)==true`， 但是 `comp(v2, v1)`的值也是 `true`，当我们把代码中的等号 `=` 去掉以后，也就满足了条件2，另外在复杂的比价逻辑中，条件3的传递性问题也是需要注意的问题。

# 构造一个崩溃的示例 #

理解了前面崩溃的原因，我们就不需要猜了，可以直接构造一个百分之百奔溃的测试用例，因为前16（`_S_threshold`）个元素会使用正常的插入排序，后面的元素才会使用无保护的插入排序，我们其实构造一个17个相同元素的vector就可以了，下面我们来试一下：

int main()
    { 
        std::vector<int> values{ 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6};
        std::sort(values.begin(), values.end(), [](int v1, int v2){ 
            return v1 >= v2;
        });
    
        for (auto v : values) std::cout << v << std::endl;
    
        return 0;
    }

运行结果如下：

albert@home-pc:/data/cpp$ g++ testsort.cpp --std=c++11 -g
    albert@home-pc:/data/cpp$ ./a.out
    0
    6
    6
    6
    6
    6
    6
    6
    6
    6
    6
    6
    6
    6
    6
    6
    6
    *** Error in `./a.out': double free or corruption (out): 0x0000000001fd9c20 ***
    ======= Backtrace: =========
    /lib/x86_64-linux-gnu/libc.so.6(+0x777f5)[0x7feaf8ef77f5]
    /lib/x86_64-linux-gnu/libc.so.6(+0x8038a)[0x7feaf8f0038a]
    /lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7feaf8f0458c]
    ./a.out[0x402446]
    ./a.out[0x40230f]
    ./a.out[0x40218a]
    ./a.out[0x402005]
    ./a.out[0x401e65]
    ./a.out[0x400bf1]
    /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7feaf8ea0840]
    ./a.out[0x4009e9]
    ======= Memory map: ========
    00400000-00403000 r-xp 00000000 00:00 211636                     /mnt/d/data/cpp/testsort/a.out
    00403000-00404000 r-xp 00003000 00:00 211636                     /mnt/d/data/cpp/testsort/a.out
    00603000-00604000 r--p 00003000 00:00 211636                     /mnt/d/data/cpp/testsort/a.out
    00604000-00605000 rw-p 00004000 00:00 211636                     /mnt/d/data/cpp/testsort/a.out
    01fc8000-01ffa000 rw-p 00000000 00:00 0                          [heap]
    7feaf4000000-7feaf4021000 rw-p 00000000 00:00 0
    7feaf4021000-7feaf8000000 ---p 00000000 00:00 0
    7feaf8b70000-7feaf8c78000 r-xp 00000000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
    7feaf8c78000-7feaf8c7a000 ---p 00108000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
    7feaf8c7a000-7feaf8e77000 ---p 0010a000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
    7feaf8e77000-7feaf8e78000 r--p 00107000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
    7feaf8e78000-7feaf8e79000 rw-p 00108000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
    7feaf8e80000-7feaf9040000 r-xp 00000000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
    7feaf9040000-7feaf9049000 ---p 001c0000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
    7feaf9049000-7feaf9240000 ---p 001c9000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
    7feaf9240000-7feaf9244000 r--p 001c0000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
    7feaf9244000-7feaf9246000 rw-p 001c4000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
    7feaf9246000-7feaf924a000 rw-p 00000000 00:00 0
    7feaf9250000-7feaf9266000 r-xp 00000000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
    7feaf9266000-7feaf9465000 ---p 00016000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
    7feaf9465000-7feaf9466000 rw-p 00015000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
    7feaf9470000-7feaf95e2000 r-xp 00000000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
    7feaf95e2000-7feaf95ef000 ---p 00172000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
    7feaf95ef000-7feaf97e2000 ---p 0017f000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
    7feaf97e2000-7feaf97ec000 r--p 00172000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
    7feaf97ec000-7feaf97ee000 rw-p 0017c000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
    7feaf97ee000-7feaf97f2000 rw-p 00000000 00:00 0
    7feaf9800000-7feaf9825000 r-xp 00000000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
    7feaf9825000-7feaf9826000 r-xp 00025000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
    7feaf9a25000-7feaf9a26000 r--p 00025000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
    7feaf9a26000-7feaf9a27000 rw-p 00026000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
    7feaf9a27000-7feaf9a28000 rw-p 00000000 00:00 0
    7feaf9bc0000-7feaf9bc1000 rw-p 00000000 00:00 0
    7feaf9bd0000-7feaf9bd2000 rw-p 00000000 00:00 0
    7feaf9be0000-7feaf9be1000 rw-p 00000000 00:00 0
    7feaf9bf0000-7feaf9bf1000 rw-p 00000000 00:00 0
    7feaf9c00000-7feaf9c01000 rw-p 00000000 00:00 0
    7feaf9c10000-7feaf9c11000 rw-p 00000000 00:00 0
    7ffffb85e000-7ffffc05e000 rw-p 00000000 00:00 0                  [stack]
    7ffffc61d000-7ffffc61e000 r-xp 00000000 00:00 0                  [vdso]
    Aborted (core dumped)

完全符合预期，如果再删除vector中的一个元素就不会崩溃了。

# 平台差异 #

这篇文章的代码编译和运行都是在Linux下完成的，但是我之前在Windows上测试时，可不需要最少17个元素的前提，这是为什么呢？因为在微软这一套编译环境下，直接检测了Compare中的条件2，并且是以断言的方式给出提示的，所以与Linux上的运行表现还有一些差异。

# 总结 #

*  使用 `std::sort` 函数自定义比较函数时，需要满足严格弱排序性，若 `comp(a, b)==true` 则 `comp(b, a)==false`，那么在比较函数中两个元素相等的情况要返回false
 *  使用 `std::sort` 函数出现崩溃是往往是不满足严格若排序性，但是在复杂的比较函数中也可能不满足传递性
 *  `std::sort` 为了把排序效率提高到极致，综合使用了快排、堆排、插入排序等多种排序方法
 *  `std::sort` 在不同的平台实现不同，当比较函数不满足严格若排序时，gcc环境下至少有17个元素才会崩溃，而 `MSVC` 则在Debug时没有元素个数限制，会通过断言直接判断这个条件是否满足

--------------------

[ ==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<== ][_ _]

--------------------

> 可是啊 总有那风吹不散的认真 总有大雨也不能抹去的泪痕~

[Compare]: https://en.cppreference.com/w/cpp/named_req/Compare
[_ _]: https://blog.csdn.net/albertsh/article/details/119090991