C++ sort函数工作原理及arr、arr+n参数含义详解

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);
 
    cout << "\nArray after sorting using "
            "default sort is : \n";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
 
    return 0;
}

1. sort函数的工作机制 #

这里调用的是C++标准库的std::sort，当前主流STL实现中它采用内省排序（Introsort） 作为核心算法，是多种排序算法的组合优化方案：

• 默认采用快速排序的分区逻辑处理大数据段，平均时间复杂度为O(nlogn)
• 当递归深度超过log2(待排序元素个数)时，自动切换为堆排序，避免快速排序最坏情况退化为O(n²)的问题
• 当待排序的子段长度小于阈值（通常为16或32）时，切换为插入排序，小数据场景下插入排序的常数开销远低于其他O(nlogn)级别的排序算法
  默认使用<运算符做大小比较，因此上述代码输出的是升序排序后的数组。

2. 第一个参数直接传数组名arr而非数组下标的原因 #

std::sort要求第一个入参是指向待排序范围起始位置的向前迭代器：
C++中数组名在绝大多数语境下会隐式退化为指向数组首元素的指针，此处arr直接等价于&arr[0]，刚好指向待排序数组的第一个元素，完全符合起始迭代器的要求，不需要额外取下标再取地址。

3. 第二个参数arr + n的作用与含义 #

std::sort的第二个入参是尾后迭代器，遵循标准库的左闭右开区间设计：
待排序的范围是[起始迭代器, 尾后迭代器)，即包含起始迭代器指向的元素，不包含尾后迭代器指向的元素。这里n是数组的总元素个数，arr + n是刚好越过数组最后一个有效元素arr[n-1]的内存地址，作为尾后迭代器传入后，整个数组的所有元素都会被纳入排序范围。

内容的提问来源于stack exchange，提问作者Anurag Patil