C++ STL(Standard Template Library)是C++标准库中的一个重要组成部分,提供了丰富的模板函数和容器,用于处理各种数据结构和算法。在STL中,排序、算数和集合算法是常用的功能,可以帮助我们对数据进行排序、统计、查找以及集合操作等。
STL提供的这些算法,能够满足各种数据处理和分析的需求。通过灵活使用这些算法,我们可以高效地对数据进行排序、查找和聚合操作,提高代码的性能和可读性。在实际编程中,根据具体问题的需求选择合适的算法,能够更好地发挥STL的优势,提高程序的效率。
9.1 堆排序算法
Sort_heap 算法函数,用于对堆容器进行排序。sort_heap的用法如下:
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
其中,first、last
是随机访问迭代器,表示待排序的堆容器的范围。sort_heap
函数将[first, last]
范围的堆容器排序,并将排序后的结果存储在相同的容器中。
读者需要注意,sort_heap
函数执行前,必须先使用make_heap
函数对容器进行堆化,然后再利用堆排序算法对其进行排序。
sort_heap函数通过重复执行pop_heap
操作来实现排序。pop_heap
操作从堆顶提取元素,将该元素放到容器的末尾位置;然后重新调整剩余元素的顺序,使之形成新的堆结构。重复执行pop_heap
操作,就可以将堆容器中的所有元素按照递增顺序排序。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void MyPrint(int val){ cout << val << " "; }
int main(int argc, char* argv[])
{
vector<int> var {45,76,89,32,11,23,45,9,0,3};
for_each(var.begin(), var.end(), MyPrint);
cout << endl;
// 建立堆
make_heap(var.begin(), var.end());
// 如果堆建立成功,则执行排序
if (is_heap(var.begin(), var.end()))
{
// 开始对堆排序
sort_heap(var.begin(), var.end());
}
for_each(var.begin(), var.end(), MyPrint);
system("pause");
return 0;
}
9.2 局部排序与复制
Partial_sort 算法函数,用于对指定区间的元素进行部分排序。partial_sort的用法如下:
template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
其中,first、last
是随机访问迭代器,表示待排序序列的范围;middle
是迭代器,表示指定的部分排序位置。partial_sort
函数将[first, last]
范围内的元素进行部分排序,使得从[first, middle)
的元素按照递增顺序排列,其余元素不保证有序。也就是说,middle
之前的元素是排过序的,middle
之后的元素未排序。
由于该函数使用的是堆排序算法。在实现排序功能前,partial_sort
函数首先将元素按照一定规则生成部分堆,然后重复执行pop_heap
操作,将堆顶元素放到middle
前,重新调整剩余元素的顺序,使之形成新的堆结构。重复执行pop_heap
操作,就可以将[first, middle)
范围内的元素按照递增顺序排列。
该算法可实现对容器中部分元素进行排序,还可以将结果拷贝到其他容器中,如下是一个简单的局部排序与排序拷贝案例。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void MyPrint(int val){ cout << val << " "; }
int main(int argc, char* argv[])
{
int iArray[] = { 3, 4, 8, 23, 56, 3, 89, 0, 32, 6 };
const int len = sizeof(iArray) / sizeof(int);
// 输出排序前的顺序
for_each(iArray, iArray + len, MyPrint);
cout << endl;
// 局部排序,将数组中的前6个元素进行排序,后面的不排列
int middle = 5; // 指定排序索引,索引从0开始
partial_sort(iArray, iArray + middle, iArray + len);
for_each(iArray, iArray + len, MyPrint);
cout << endl;
// 排序并拷贝元素,将iArray中前5个元素排序后拷贝到var中
vector<int> var(6);
partial_sort_copy(iArray, iArray + 5, var.begin(), var.end());
for_each(iArray, iArray + 5, MyPrint);
system("pause");
return 0;
}
9.3 快速排序算法
Sort 算法函数,用于对序列进行排序。sort的用法如下:
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
其中,first、last
是随机访问迭代器,表示待排序的序列的范围。sort函数将[first, last]
范围内的元素按照递增顺序排序,并将排序后的结果存储在相同的容器中。sort函数在执行前,需要保证所排序的元素类型支持<
运算符。
sort函数使用的是快速排序算法,在实现排序功能前,sort函数首先会选择[first, last]
范围内的一个元素作为分割基准元素,然后按照分割基准元素将范围内的元素分为两个序列,其中一个序列的元素均小于基准元素,另一个序列的元素均大于等于基准元素。然后对两个序列分别递归调用sort
函数,不断进行分割和排序,直到分割出的序列长度为1,排序就完成了。
#include <iostream>
#include <algorithm>
#include <vector>
#includ