C++排序详解：sort函数与自定义cmp

"排序和cmp函数在C++中的应用与实践" 在C++编程语言中，排序是一个常见的操作，尤其在处理数组、结构体等数据集合时。本资源主要讲解了两种常用的排序方法：内置的`sort`函数以及桶排序算法，并涉及到自定义比较函数`cmp`的使用。 一、`sort`排序 `sort`函数是C++标准库中的一个成员，位于`<algorithm>`头文件中。它提供了一种高效且灵活的方式来对序列进行排序，其时间复杂度通常为O(n*log(n))。 1. `sort`的基本用法： - 参数1：要排序的序列的起始迭代器。 - 参数2：序列的结束迭代器（不包括该位置的元素）。 - 参数3：可选的排序规则，默认为升序排序。 示例代码： ```cpp int a[] = {2, 7, 1, 5, 0}; sort(a, a + 5); // 默认升序排序 ``` 2. 自定义排序规则： - 如果需要自定义排序规则，例如降序排序或按照结构体中的某个字段排序，可以通过传递一个比较函数对象（如`less`或`greater`）或者自定义的`cmp`函数来实现。 示例代码（结构体排序）： ```cpp typedef struct stu { int xuehao; int chengji; } stu; stu p[20]; bool cmp1(stu a, stu b) { return a.chengji > b.chengji; // 降序按成绩排序 } sort(p, p + 20, cmp1); ``` 二、`cmp`函数 `cmp`函数是自定义比较函数，用于指定排序时元素的比较规则。当`sort`函数的第三个参数传入`cmp`函数时，会根据`cmp`返回值决定元素的相对顺序。 - 如果`cmp(a, b)`返回`true`，那么`a`将被放在`b`之前。 - 当`cmp`函数中两个元素相等时，排序的稳定性取决于`sort`函数的实现，即相等元素的相对顺序可能会保持不变，也可能发生变化。 三、桶排序 桶排序是一种非比较型排序算法，适用于数据范围有限且均匀分布的情况。通过将数据分配到多个“桶”中，每个桶再分别排序，最后再合并所有桶中的结果。 1. 示例：对于[0, 10]范围内的分数，可以创建一个大小为11的桶数组，每个桶代表一个分数段。遍历原始数据，将每个分数放入对应的桶中。然后，依次遍历桶并收集排序后的结果。 2. 实现步骤： - 初始化空桶。 - 将每个元素放入对应的桶中。 - 对每个非空桶进行排序，可以递归使用桶排序，或者选择其他排序算法。 - 合并所有桶中的元素，得到最终排序的结果。 总结，`sort`函数和自定义`cmp`函数提供了强大的排序能力，而桶排序则在特定情况下能提供线性时间复杂度的排序效率。了解和熟练掌握这些排序方法，将有助于解决各种实际编程问题。