STL algorithm详解：sort, stable_sort与堆排序示例

在C++标准模板库（STL）中，`algorithm`模块提供了丰富的排序算法，这些函数对于处理容器中的元素并保持数据结构的有序性至关重要。本文主要关注`sort()`、`stable_sort()`以及`sort_heap()`这三种函数，并通过实际代码示例来解释它们的用法。 1. `sort()`函数： - 该函数是C++ STL中最常用的排序函数，采用的是快速排序算法，平均时间复杂度为O(NlogN)，其中N表示待排序元素的数量。`sort()`默认使用`less<T>()`作为比较函数，这意味着它会按升序对元素进行排序。 - 使用`sort(a, a+len);`对数组进行排序，`a`是数组的起始地址，`len`是元素个数。例如，以下代码对整数数组进行升序排序： ```cpp int a[] = {3, 1, 4, 2, 5}; int len = sizeof(a) / sizeof(int); sort(a, a+len); ``` 输出结果将是：1 2 3 4 5。 2. `stable_sort()`函数： - 与`sort()`不同，`stable_sort()`保证了相等元素的相对顺序不会改变，即稳定性。时间复杂度通常为O(NlogN)，但在最坏情况下可能会达到O(N(logN)^2)。当需要保持相等元素的原始顺序时，应使用此函数。 - 使用`stable_sort(a, a+len, myGreater);`可以自定义比较函数，如`myGreater()`，对数组进行降序排序。这里`myGreater()`函数必须遵循相应的比较规则。 ```cpp bool myGreater(int& a, int& b) { return a > b; } stable_sort(a, a+len, myGreater); ``` 输出结果将是：5 4 3 2 1。 3. `sort_heap()`函数： - `sort_heap()`用于对已排序的堆进行调整，使之符合排序的要求。由于堆本身已经实现了部分有序性，因此其操作时间复杂度仍为O(NlogN)。在使用前，需要先调用`make_heap()`将数据转换成堆结构。 - 示例中，首先创建一个自定义比较函数`myGreater(int*, int*)`，然后将其传递给`make_heap()`和`sort_heap()`，实现降序排序： ```cpp bool myGreater(int* a, int* b) { return *a > *b; } make_heap(a, a+len, myGreater); sort_heap(a, a+len, myGreater); ``` 注意，这里假设`a`是存放堆元素的指针，而不是整个数组。输出结果将是堆顶元素最大，依次递减。 总结，`algorithm`模块中的`sort()`、`stable_sort()`和`sort_heap()`函数提供了不同的排序策略，适用于不同的场景。掌握它们的用法对于编写高效且稳定的C++代码至关重要。在实际应用中，选择合适的排序函数能有效提升程序性能，并确保数据的正确排序。