设为首页 加入收藏

TOP

9.1 C++ STL 排序、算数与集合(一)
2023-08-26 21:10:35 】 浏览:225
Tags:9.1 STL 排序

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
首页 上一页 1 2 3 4 5 下一页 尾页 1/5/5
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++项目实战之演讲比赛流程管理系.. 下一篇使用C++界面框架ImGUI开发一个简..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目