1. std::less

   • 功能描述：这是std::sort默认使用的比较准则。它定义了一种从小到大（升序）的排序规则。例如，对于两个整数a和b，std::less<int>()会在a < b时返回true，表示a应该排在b之前。
   • 示例代码：

   #include <iostream>
   #include <algorithm>
   int main() {
       int arr[] = {5, 3, 8, 4, 2};
       int n = sizeof(arr)/sizeof(arr[0]);
       std::sort(arr, arr + n, std::less<int>());
       for (int i = 0; i < n; ++i) {
           std::cout << arr[i] << " ";
       }
       std::cout << std::endl;
       return 0;
   }
   

   在这个示例中，数组arr将按照升序进行排序，输出结果为2 3 4 5 8。

2. 自定义比较函数（函数指针方式）

   • 功能描述：可以自己定义一个比较函数，该函数接受两个参数（通常是数组中的元素类型），并返回一个bool值。如果返回true，表示第一个参数应该排在第二个参数之前。
   • 示例代码：

   #include <iostream>
   #include <algorithm>
   bool customCompare(int a, int b) {
       return a % 2 < b % 2;  // 按照元素的奇偶性排序，偶数排在奇数之前
   }
   int main() {
       int arr[] = {5, 3, 8, 4, 2};
       int n = sizeof(arr)/sizeof(arr[0]);
       std::sort(arr, arr + n, customCompare);
       for (int i = 0; i < n; ++i) {
           std::cout << arr[i] << " ";
       }
       std::cout << std::endl;
       return 0;
   }
   

   在这个示例中，自定义的customCompare函数按照元素的奇偶性进行排序。先比较元素对2取模后的结果，偶数（对2取模为0）会排在奇数（对2取模为1）之前。输出结果可能是8 4 2 5 3（具体顺序可能因初始数组顺序等因素略有不同）。

3. 自定义比较函数对象（通过结构体或类重载()运算符）

   • 功能描述：可以定义一个结构体或类，在其中重载()运算符，使其可以像函数一样被调用。这个重载的函数实现比较逻辑。
   • 示例代码：

   #include <iostream>
   #include <algorithm>
   struct CustomCompareObject {
       bool operator()(int a, int b) const {
           return a > b;  // 按照从大到小的顺序排序
       }
   };
   int main() {
       int arr[] = {5, 3, 8, 4, 2};
       int n = sizeof(arr)/sizeof(arr[0]);
       std::sort(arr, arr + n, CustomCompareObject());
       for (int i = 0; i < n; ++i) {
           std::cout << arr[i] << " ";
       }
       std::cout << std::endl;
       return 0;
   }
   

   这里定义了CustomCompareObject结构体，通过重载()运算符实现了从大到小的比较逻辑。将这个结构体的实例（CustomCompareObject()）传递给std::sort函数，就可以按照自定义的从大到小的规则对数组进行排序，输出结果为8 5 4 3 2。

1. 基本概念

   • sizeof是C和C++ 中的一个操作符，它用于获取数据类型或者变量所占用的字节数。字节数的大小取决于编译器和目标平台，例如在32位系统和64位系统中，一些数据类型的字节数可能会不同。

2. 语法格式

   • sizeof(类型名)或者sizeof(变量名)。
   • 例如：sizeof(int)可以获取int类型占用的字节数；sizeof(myVariable)可以获取变量myVariable占用的字节数。

3. 用于基本数据类型

   • 整数类型
     • 在大多数32位系统中，sizeof(char)通常是1字节，因为char类型用于存储单个字符。sizeof(int)一般是4字节，int类型用于存储整数。sizeof(long)可能是4字节或者8字节，具体取决于编译器和系统。例如：

     #include <iostream>
     int main() {
         std::cout << "sizeof(char): " << sizeof(char) << " bytes" << std::endl;
         std::cout << "sizeof(int): " << sizeof(int) << " bytes" << std::endl;
         std::cout << "sizeof(long): " << sizeof(long) << " bytes" << std::endl;
         return 0;
     }
     

   • 浮点数类型
     • sizeof(float)在大多数系统中是4字节，用于存储单精度浮点数；sizeof(double)通常是8字节，用于存储双精度浮点数。例如：

     #include <iostream>
     int main() {
         std::cout << "sizeof(float): " << sizeof(float) << " bytes" << std::endl;
         std::cout << "sizeof(double): " << sizeof(double) << " bytes" << std::endl;
         return 0;
     }
     

   • 指针类型
     • 在32位系统中，指针类型（如int*、char*等）通常占用4字节，因为32位地址空间可以用4字节来表示内存地址。在64位系统中，指针类型一般占用8字节，因为64位地址空间需要8字节来表示内存地址。例如：

     #include <iostream>
     int main() {
         int* ptr;
         std::cout << "sizeof(int*): " << sizeof(int*) << " bytes" << std::endl;
         char* charPtr;
         std::cout << "sizeof(char*): " << sizeof(char*) << " bytes" << std::endl;
         return 0;
     }
     

4. 用于数组

   • 当sizeof用于数组时，它返回整个数组所占用的字节数。对于一维数组，计算公式是sizeof(数组名)=数组元素类型占用字节数×数组元素个数。例如：

   #include <iostream>
   int main() {
       int arr[] = {1, 2, 3, 4, 5};
       std::cout << "sizeof(arr): " << sizeof(arr) << " bytes" << std::endl;
       std::cout << "Number of elements in arr: " << sizeof(arr)/sizeof(arr[0]) << std::endl;
       return 0;
   }
   

   • 这里sizeof(arr)返回整个数组占用的字节数，sizeof(arr[0])返回数组中单个元素（这里是int类型）占用的字节数，通过sizeof(arr)/sizeof(arr[0])可以计算出数组元素的个数。

5. 用于结构体和联合体

   • 结构体
     • 对于结构体，sizeof返回结构体对象所占用的总字节数。结构体的大小可能会受到对齐方式（alignment）的影响。例如：

     #include <iostream>
     struct MyStruct {
         int a;
         char b;
     };
     int main() {
         std::cout << "sizeof(MyStruct): " << sizeof(MyStruct) << " bytes" << std::endl;
         return 0;
     }
     

     • 这里MyStruct结构体包含一个int类型成员和一个char类型成员。由于内存对齐的原因，int类型通常会占用4字节且在内存中以4字节对齐，所以这个结构体的大小可能不是简单的sizeof(int)+sizeof(char)，而是会根据编译器的对齐规则进行填充，实际大小可能大于这个和。
   • 联合体
     • 联合体（union）的sizeof返回联合体所占用的字节数，其大小取决于联合体中最大成员的大小。例如：

     #include <iostream>
     union MyUnion {
         int a;
         double b;
     };
     int main() {
         std::cout << "sizeof(MyUnion): " << sizeof(MyUnion) << " bytes" << std::endl;
         return 0;
     }
     

     • 这里MyUnion联合体包含一个int类型成员和一个double类型成员，因为double类型占用字节数较多（通常8字节），所以sizeof(MyUnion)返回的值是8字节。

1. sort函数默认使用的排序算法

   • C++标准库中的sort函数通常采用的是一种经过优化的快速排序（Quick Sort）算法，其平均时间复杂度为 $O(n log n)$。但是，在某些情况下，为了避免快速排序的最坏情况（时间复杂度退化为 $O(n^2)$，例如数据已经有序或接近有序的情况），它可能会切换到插入排序（Insertion Sort）。当待排序的子序列规模较小时（具体的阈值由实现决定，不同的编译器或标准库实现可能不同），插入排序的效率可能更高，所以sort函数会结合这两种排序算法来提高整体性能。

2. 快速排序的基本原理（sort函数主要部分）

   • 划分（Partition）步骤
     • 快速排序首先会选择一个基准元素（pivot）。例如，在简单的实现中，可以选择序列的第一个元素或者随机选择一个元素作为基准。
     • 然后将序列中的元素重新排列，使得所有小于基准元素的元素都移到基准元素的左边，所有大于基准元素的元素都移到基准元素的右边。这个过程称为划分。例如，对于序列[5, 3, 8, 4, 2]，如果选择5作为基准元素，经过划分后可能得到[3, 4, 2, 5, 8]。
   • 递归排序子序列
     • 在划分完成后，得到了两个子序列（左边小于基准的子序列和右边大于基准的子序列）。然后对这两个子序列分别进行快速排序，即递归地调用快速排序函数。例如，对于刚才得到的子序列[3, 4, 2]和[8]，会继续对[3, 4, 2]进行划分和递归排序，直到子序列的长度为1或者0，此时整个序列就完成了排序。

3. 插入排序的基本原理（sort函数辅助部分）

   • 插入排序是一种简单的排序算法，它的基本思想是将一个元素插入到已经排好序的序列中的合适位置。
   • 例如，对于序列[3, 5, 4, 2]，假设前面的[3, 5]已经是排好序的部分。当考虑元素4时，它会从后往前与已排序的元素进行比较，将4插入到3和5之间，得到[3, 4, 5, 2]。然后再考虑元素2，同样的方式将其插入到合适的位置，最终得到[2, 3, 4, 5]。

4. 不同编译器或标准库实现可能的差异

   • 虽然C++标准规定了sort函数的行为（如排序后的序列是升序等），但对于具体使用的算法细节和优化策略并没有严格规定。不同的编译器或标准库实现可能会根据自身的设计和性能优化目标来选择具体的实现方式。例如，有些实现可能会在多线程环境下对sort函数进行优化，利用多核处理器来提高排序速度；有些可能会对特定的数据分布（如已经接近有序的数据）采用更高效的处理策略。

1. 使用函数对象（仿函数）来定义排序规则
   • 基本原理
     • 函数对象是一个类，它重载了()运算符，使得这个类的对象可以像函数一样被调用。通过创建一个函数对象类来定义排序规则，然后将这个函数对象传递给sort函数作为比较器。
   • 示例代码（以对整数数组进行降序排序为例）

     #include <iostream>
     #include <algorithm>
     class GreaterThan {
     public:
         bool operator()(int a, int b) const {
             return a > b;
         }
     };
     int main() {
         int arr[] = {5, 3, 8, 4, 2};
         int n = sizeof(arr) / sizeof(arr[0]);
         std::sort(arr, arr + n, GreaterThan());
         for (int i = 0; i < n; ++i) {
             std::cout << arr[i] << " ";
         }
         std::cout << std::endl;
         return 0;
     }
     

   • 解释
     • 首先定义了一个名为GreaterThan的类，它有一个重载的()运算符。这个运算符接受两个整数a和b，并返回a > b的结果。
     • 在main函数中，当调用std::sort(arr, arr + n, GreaterThan());时，GreaterThan()创建了一个函数对象作为比较器传递给sort函数。sort函数在比较元素时会调用这个函数对象的()运算符，按照a > b的规则进行比较，从而实现降序排序。
2. 使用普通函数来定义排序规则
   • 基本原理
     • 创建一个普通函数，该函数接受两个要比较的元素作为参数，根据自定义的规则返回比较结果。然后将这个函数的名称传递给sort函数作为比较器。
   • 示例代码（以对包含学生信息的结构体数组按照成绩降序排序为例）

     #include <iostream>
     #include <algorithm>
     #include <string>
     struct Student {
         std::string name;
         int score;
     };
     bool compareStudents(const Student& s1, const Student& s2) {
         return s1.score > s2.score;
     }
     int main() {
         Student students[] = {{"Alice", 90}, {"Bob", 80}, {"Charlie", 95}};
         int n = sizeof(students) / sizeof(students[0]);
         std::sort(students.begin(), students.end(), compareStudents);
         for (int i = 0; i < n; ++i) {
             std::cout << students[i].name << " " << students[i].score << std::endl;
         }
         return 0;
     }
     

   • 解释
     • 定义了一个Student结构体，包含姓名和成绩两个成员。
     • 然后定义了一个名为compareStudents的普通函数，它接受两个const Student&类型的参数，比较这两个学生的成绩，并返回s1.score > s2.score的结果。
     • 在main函数中，调用std::sort(students.begin(), students.end(), compareStudents);，将compareStudents函数作为比较器传递给sort函数。sort函数在比较两个Student结构体元素时，会调用compareStudents函数，按照成绩降序的规则进行排序。
3. 使用Lambda表达式来定义排序规则（C++ 11及以上）
   • 基本原理
     • Lambda表达式是一种匿名函数，它可以在需要函数的地方直接定义函数逻辑。可以使用Lambda表达式简洁地定义排序规则，并将其传递给sort函数。
   • 示例代码（以对字符串数组按照字符串长度升序排序为例）

     #include <iostream>
     #include <algorithm>
     #include <string>
     int main() {
         std::string arr[] = {"apple", "banana", "pear", "kiwi"};
         int n = sizeof(arr) / sizeof(arr[0]);
         std::sort(arr.begin(), arr.end(), [](const std::string& s1, const std::string& s2) {
             return s1.length() < s2.length();
         });
         for (int i = 0; i < n; ++i) {
             std::cout << arr[i] << " ";
         }
         std::cout << std::endl;
         return 0;
     }
     

   • 解释
     • 在调用std::sort(arr.begin(), arr.end(), [](const std::string& s1, const std::string& s2) {... });时，[]中的内容是Lambda表达式的捕获列表（这里为空，表示不捕获任何外部变量），后面的(const std::string& s1, const std::string& s2)是参数列表，{return s1.length() < s2.length();}是函数体。这个Lambda表达式定义了比较两个字符串长度的规则，按照长度升序排序。sort函数会使用这个规则对字符串数组进行排序。

1. 对vector容器排序（以vector存储整数为例）
   • 示例代码

     #include <iostream>
     #include <algorithm>
     #include <vector>
     int main() {
         std::vector<int> vec = {5, 3, 8, 4, 2};
         std::sort(vec.begin(), vec.end());
         for (int num : vec) {
             std::cout << num << " ";
         }
         std::cout << std::endl;
         return 0;
     }
     

   • 解释
     • 首先包含了<iostream>用于输出，<algorithm>用于sort函数，<vector>用于vector容器。
     • 创建了一个std::vector<int>类型的容器vec，并初始化了一些整数元素。
     • std::sort(vec.begin(), vec.end());用于对vec容器中的元素进行排序。vec.begin()返回指向容器第一个元素的迭代器，vec.end()返回指向容器最后一个元素之后位置的迭代器，这两个迭代器确定了要排序的元素范围。
     • 最后通过范围for循环遍历排序后的vec容器，并输出每个元素。
2. 对vector容器中自定义结构体的排序（以存储学生信息的结构体为例）
   • 示例代码

     #include <iostream>
     #include <algorithm>
     #include <vector>
     #include <string>
     struct Student {
         std::string name;
         int age;
         int score;
     };
     bool compareStudents(const Student& s1, const Student& s2) {
         if (s1.score!= s2.score) {
             return s1.score > s2.score;
         } else {
             return s1.age < s2.age;
         }
     }
     int main() {
         std::vector<Student> students;
         students.push_back({"Alice", 20, 90});
         students.push_back({"Bob", 22, 90});
         students.push_back({"Charlie", 21, 85});
         std::sort(students.begin(), students.end(), compareStudents);
         for (const Student& student : students) {
             std::cout << student.name << " " << student.age << " " << student.score << std::endl;
         }
         return 0;
     }
     

   • 解释
     • 定义了Student结构体，包含姓名、年龄和成绩三个成员。
     • 定义了compareStudents函数用于比较两个Student结构体对象。在函数中，首先根据成绩进行比较，如果成绩不同，按照成绩从高到低排序；如果成绩相同，再按照年龄从小到大排序。
     • 在main函数中，创建了std::vector<Student>类型的容器students，并通过push_back方法添加了几个Student对象。
     • 使用std::sort(students.begin(), students.end(), compareStudents);对students容器中的元素进行排序，排序规则由compareStudents函数定义。
     • 最后通过范围for循环遍历排序后的students容器，输出每个学生的信息。
3. 对list容器排序（list是双向链表容器）
   • 示例代码

     #include <iostream>
     #include <algorithm>
     #include <list>
     int main() {
         std::list<int> myList = {5, 3, 8, 4, 2};
         myList.sort();
         for (int num : myList) {
             std::cout << num << " ";
         }
         std::cout << std::endl;
         return 0;
     }
     

   • 解释
     • 包含<iostream>、<algorithm>和<list>头文件。
     • 创建了一个std::list<int>类型的容器myList，并初始化了一些整数元素。
     • 对于list容器，可以直接使用myList.sort();进行排序，这是因为list容器有自己的sort成员函数，它会对容器内的元素进行排序。其默认排序规则是升序排列。
     • 最后通过范围for循环遍历排序后的myList容器，输出每个元素。
4. 对deque容器排序（deque是双端队列容器）
   • 示例代码

     #include <iostream>
     #include <algorithm>
     #include <deque>
     int main() {
         std::deque<int> myDeque = {5, 3, 8, 4, 2};
         std::sort(myDeque.begin(), myDeque.end());
         for (int num : myDeque) {
             std::cout << num << " ";
         }
         std::cout << std::endl;
         return 0;
     }
     

   • 解释
     • 包含相关头文件<iostream>、<algorithm>和<deque>。
     • 创建了一个std::deque<int>类型的容器myDeque，并初始化了一些整数元素。
     • 使用std::sort(myDeque.begin(), myDeque.end());对myDeque容器中的元素进行排序，其原理和对vector容器排序类似，通过迭代器指定排序范围。
     • 最后通过范围for循环遍历排序后的myDeque容器，输出每个元素。

以下是一个通俗易懂的C++ sort函数教程：

1. 基本概念

• sort函数是C++标准库中的一个强大的排序工具，它定义在<algorithm>头文件中，使用时需加上std::命名空间，或者使用using namespace std;语句.
• 它采用了类似于快速排序的算法，平均时间复杂度为$O(n log n)$，能够高效地对给定范围内的元素进行排序.

2. 基本用法

• 对于简单的数组排序，sort函数的使用非常简单。以下是一个对整数数组进行升序排序的示例：

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::sort(arr, arr + n);
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

在上述代码中，sort(arr, arr + n);表示对数组arr从起始位置arr到结束位置arr + n（不包括arr + n所指向的元素）进行排序。排序后，数组中的元素将按照升序排列.

3. 降序排序

• 如果想要实现降序排序，可以使用greater<>()函数作为sort函数的第三个参数。示例如下：

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::sort(arr, arr + n, std::greater<int>());
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

这里std::greater<int>()是一个函数对象，它定义了int类型元素的大于比较规则，从而使得sort函数按照降序对数组进行排序.

4. 自定义比较函数

• 当需要按照特定的规则进行排序时，可以自定义比较函数，并将其作为sort函数的第三个参数。例如，对于一个包含学生信息的结构体数组，按照学生的成绩进行降序排序，如果成绩相同，则按照年龄升序排序，示例代码如下：

#include <iostream>
#include <algorithm>
#include <string>

struct Student {
    std::string name;
    int age;
    int score;
};

bool compareStudents(const Student& s1, const Student& s2) {
    if (s1.score!= s2.score) {
        return s1.score > s2.score;
    } else {
        return s1.age < s2.age;
    }
}

int main() {
    Student students[] = {{"Alice", 20, 90}, {"Bob", 22, 90}, {"Charlie", 21, 85}};
    int n = sizeof(students) / sizeof(students[0]);
    std::sort(students, students + n, compareStudents);
    for (int i = 0; i < n; ++i) {
        std::cout << students[i].name << " " << students[i].age << " " << students[i].score << std::endl;
    }
    return 0;
}

在compareStudents函数中，首先比较学生的成绩，如果成绩不同，则按照成绩降序排列；如果成绩相同，则比较年龄，按照年龄升序排列。这样，sort函数就会根据自定义的比较函数对学生数组进行排序.

5. 对部分区间排序

• sort函数还可以对数组的指定区间进行排序。例如，只对数组arr中从索引2到末尾的元素进行排序，可以这样写：

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {0, 1, 5, 8, 9, 6, 7, 3, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::sort(arr + 2, arr + n);
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

上述代码中，sort(arr + 2, arr + n);表示对从arr[2]开始到arr[n - 1]结束的区间内的元素进行排序，而区间之外的元素保持不变.