学习网站:http://www.stlchina.org/twiki/bin/view.pl/Main/STLTechArticles
http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms
排序(sort):所有sort算法介绍:使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator)
1. 所有STL sort算法函数的名字列表:
函数名
|
功能描述
|
sort
|
对给定区间所有元素进行排序
|
stable_sort
|
对给定区间所有元素进行稳定排序
|
partial_sort
|
对给定区间所有元素部分排序
|
partial_sort_copy
|
对给定区间复制并排序
|
nth_element
|
找出给定区间的某个位置对应的元素
|
is_sorted
|
判断一个区间是否已经排好序
|
partition
|
使得符合某个条件的元素放在前面
|
stable_partition
|
相对稳定的使得符合某个条件的元素放在前面
|
2. 比较函数:当你需要按照某种特定方式进行排序时,你需要给sort指定比较函数,否则程序会自动提供给你一个比较函数。
vector < int > vect;
//...
sort(vect.begin(), vect.end());
//此时相当于调用
sort(vect.begin(), vect.end(), less<int>() );
sort 中的其他比较函数
equal_to
|
相等
|
not_equal_to
|
不相等
|
less
|
小于
|
greater
|
大于
|
less_equal
|
小于等于
|
greater_equal
|
大于等于
|
上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数,以下是仿函数列表:
不能直接写入仿函数的名字,而是要写其重载的()函数: less<int>();
当你的容器中元素时一些标准类型(int float char)或者string时,你可以直接使用这些函数模板。但如果你
时自己定义的类型或者你需要按照其他方式排序,你可以有两种方法来达到效果:一种是自己写比较函数。另一种是重载类型的'<'操作赋。如:
bool less_second(const myclass & m1, const myclass & m2) {
return m1.second < m2.second;
}
3. 全排序:全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序,而是结合内插排序算法)。复杂度为n*log(n).stable_sort采用的是"归并排序",分派足够内存是,其算法复杂度为n*log(n), 否则其复杂度为n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。
用于全排序的函数有:
void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
4. 局部排序:partial_sort采用的堆排序(heapsort),它在任何情况下的复杂度都是n*log(n).
局部排序其实是为了减少不必要的操作而提供的排序方式。
其函数原型为:
1) void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);
2) void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,
RandomAccessIterator last, StrictWeakOrdering comp);
3) RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,RandomAccessIterator result_last);
4) RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,RandomAccessIterator result_last, Compare comp);
用法使用情况:班上有1000个学生,我想知道分数最低的5名是哪些人。
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());
5. nth_element 指定元素排序
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last,
StrictWeakOrdering comp);
使用情况:班上有1000个学生,我想知道分数排在倒数第4名的学生。
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());
6. partition 和stable_partition :partition就是把一个区间中的元素按照某个条件分成两类,并没有排序。
其函数原型为:
ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
用法如:班上10个学生,计算所有没有及格(低于60分)的学生:
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));
7. 效率由高到低(耗时由小变大):
partion
stable_partition
nth_element
partial_sort
sort
stable_sort
8. Effective STL对如何选择排序函数总结的很好:
1) 若需对vector, string, deque, 或 array容器进行全排序,你可选择sort或stable_sort;
若只需对vector, string, deque, 或 array容器中取得top n的元素,部分排序partial_sort是首选.
若对于vector, string, deque, 或array容器,你需要找到第n个位置的元素或者你需要得到top n且不关系top
2) n中的内部顺序,nth_element是最理想的;
3) 若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开,你最好使用partition或stable_partition;
4) 若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果,你必须间接使用。
分享到:
相关推荐
本文将深入探讨C++中实现的一些常见排序算法,包括冒泡排序、快速排序和直接插入排序。这些排序算法对于理解计算机如何处理和组织大量数据至关重要。 首先,让我们来看看冒泡排序。冒泡排序是一种基础的排序算法,...
在编程领域,排序算法是计算机科学中的核心概念,特别是在C++这样的高级编程语言中。本文将深入探讨在C++中实现的几种主要排序算法,包括归并排序、插入排序、冒泡排序、希尔排序、快速排序以及桶排序,并对它们的...
《C++排序算法全集》是一个集合了多种排序算法实现的资源包,主要面向学习和研究C++编程语言以及算法的读者。在这个压缩包中,包含了一份名为"C++排序算法全集.pdf"的文档,该文档详细介绍了各种排序算法在C++中的...
在C++中实现排序算法,我们可以利用其面向对象的特性,以及STL(Standard Template Library)中的工具,如`vector`容器和`algorithm`头文件中的排序函数。不过,这个项目选择了直接实现,可能是为了更好地理解排序...
在编程领域,排序算法是数据处理的核心部分,尤其是在C++这样的高级编程语言中。本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并...
本文将深入探讨C和C++编程语言中常见的几种排序算法的设计与实现,以及它们之间的性能比较。 首先,让我们从最基础的排序算法——冒泡排序开始。冒泡排序通过不断地交换相邻的不正确顺序的元素来逐步排序数组。它的...
"C++实现分水岭算法(Watershed Algorithm)" 本文详细介绍了C++实现分水岭算法(Watershed Algorithm),该算法是一种基于拓扑理论的数学形态学的分割方法。下面是相关的知识点: 1. 分水岭算法的基本思想:将...
在C++中实现这些排序算法时,通常会用到STL(Standard Template Library)中的`algorithm`库,其中包含了一系列排序相关的函数,如`sort()`,它默认采用的是快速排序的实现,但可以被替换为自定义的排序算法。...
本主题聚焦于使用C++实现六种不同的排序算法,并应用于四种不同类型的数据。这些排序算法包括了冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,它们各自有其独特的性能特征和适用场景。以下是对这六种...
本文将深入探讨三种常见的排序算法:堆排序、快速排序,以及它们在C++语言中的实现。 首先,我们来了解堆排序。堆排序是一种基于比较的排序算法,利用了完全二叉树的特性——堆。在最大堆中,每个父节点的值都大于...
标题"排序算法之堆排序算法:用C++语言实现堆排序算法",意味着我们将讨论如何用C++编程语言来实现堆排序的过程。C++是面向对象的编程语言,具有丰富的库支持和高效的执行性能,是实现算法的理想选择。 描述"排序...
C++中的几种排序算法 C++中的几种排序算法是计算机科学中的一种基本算法,用于对数据进行排序。排序算法的选择取决于具体的应用场景和数据特点。本文将介绍C++中的几种常见的排序算法,包括插入排序、选择排序、...
在这个压缩包中,"sort_algorithm_cpp-master"目录下可能包含了以下几种经典的排序算法的C++实现: 1. **冒泡排序(Bubble Sort)**:这是一种简单直观的排序算法,通过重复遍历待排序的数列,比较相邻元素并交换...
在IT领域,排序算法是计算机科学中的基础且重要的部分,特别是在C++编程中。这个压缩包文件"Sort.cpp"显然包含了一些实现常见排序算法的C++类。让我们深入探讨一下这些排序算法及其在C++中的实现。 首先,我们来看...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的...
在C++中,最常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序以及堆排序等。每种排序算法都有其独特的优缺点,如时间复杂度、空间复杂度以及稳定性等。 1. 冒泡排序:是最简单的排序算法,通过...
本文将详细探讨在C++语言中实现的几种常见排序算法,包括快速排序、Shell排序、堆排序、折半排序、冒泡排序、归并排序以及B树的实现,并对直接排序法进行简要介绍。 1. **快速排序**:由C.A.R. Hoare提出的快速排序...
首先,让我们从基础的排序算法开始。在C++中,我们有多种排序方法,如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序。这些排序算法各有优缺点,适用于不同的场景。例如,冒泡排序和选择排序虽然实现...
首先,你会接触到排序算法,如冒泡排序、选择排序、插入排序、快速排序和归并排序,这些算法用于对数据进行有效组织,提高数据检索效率。接下来,搜索算法,如线性搜索和二分搜索,将教会你如何在数据集中查找特定...