`
strong_fee
  • 浏览: 178760 次
  • 性别: Icon_minigender_1
  • 来自: 福州
社区版块
存档分类
最新评论

C++排序算法 algorithm

阅读更多

学习网站: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容器进行全排序,你可选择sortstable_sort

若只需对vector, string, deque, array容器中取得top n的元素,部分排序partial_sort是首选.

若对于vector, string, deque, array容器,你需要找到第n个位置的元素或者你需要得到top n且不关系top

         2)      n中的内部顺序,nth_element是最理想的;

         3)      若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开,你最好使用partitionstable_partition

         4)      若使用的list容器,你可以直接使用partitionstable_partition算法,你可以使用list::sort代替sortstable_sort排序。若你需要得到partial_sortnth_element的排序效果,你必须间接使用。

分享到:
评论

相关推荐

    Sort_Algorithm_排序算法_C++_c++algorithmsort_

    本文将深入探讨C++中实现的一些常见排序算法,包括冒泡排序、快速排序和直接插入排序。这些排序算法对于理解计算机如何处理和组织大量数据至关重要。 首先,让我们来看看冒泡排序。冒泡排序是一种基础的排序算法,...

    C++排序算法对比(桶排序等)

    在编程领域,排序算法是计算机科学中的核心概念,特别是在C++这样的高级编程语言中。本文将深入探讨在C++中实现的几种主要排序算法,包括归并排序、插入排序、冒泡排序、希尔排序、快速排序以及桶排序,并对它们的...

    C++排序算法全集.rar

    《C++排序算法全集》是一个集合了多种排序算法实现的资源包,主要面向学习和研究C++编程语言以及算法的读者。在这个压缩包中,包含了一份名为"C++排序算法全集.pdf"的文档,该文档详细介绍了各种排序算法在C++中的...

    3种排序算法可视化程序 c++ 算法

    在C++中实现排序算法,我们可以利用其面向对象的特性,以及STL(Standard Template Library)中的工具,如`vector`容器和`algorithm`头文件中的排序函数。不过,这个项目选择了直接实现,可能是为了更好地理解排序...

    C++语言的算法实现包括插入排序冒泡排序堆排序快速排序

    在编程领域,排序算法是数据处理的核心部分,尤其是在C++这样的高级编程语言中。本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并...

    C C++各种排序算法设计

    本文将深入探讨C和C++编程语言中常见的几种排序算法的设计与实现,以及它们之间的性能比较。 首先,让我们从最基础的排序算法——冒泡排序开始。冒泡排序通过不断地交换相邻的不正确顺序的元素来逐步排序数组。它的...

    C++实现分水岭算法(Watershed Algorithm)

    "C++实现分水岭算法(Watershed Algorithm)" 本文详细介绍了C++实现分水岭算法(Watershed Algorithm),该算法是一种基于拓扑理论的数学形态学的分割方法。下面是相关的知识点: 1. 分水岭算法的基本思想:将...

    C++ 排序 算法 快排 冒泡 希尔 堆排

    在C++中实现这些排序算法时,通常会用到STL(Standard Template Library)中的`algorithm`库,其中包含了一系列排序相关的函数,如`sort()`,它默认采用的是快速排序的实现,但可以被替换为自定义的排序算法。...

    C++实现6种排序算法对四种类型数据排序

    本主题聚焦于使用C++实现六种不同的排序算法,并应用于四种不同类型的数据。这些排序算法包括了冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,它们各自有其独特的性能特征和适用场景。以下是对这六种...

    排序算法实现_C++

    本文将深入探讨三种常见的排序算法:堆排序、快速排序,以及它们在C++语言中的实现。 首先,我们来了解堆排序。堆排序是一种基于比较的排序算法,利用了完全二叉树的特性——堆。在最大堆中,每个父节点的值都大于...

    排序算法之堆排序算法:用C++语言实现堆排序算法

    标题"排序算法之堆排序算法:用C++语言实现堆排序算法",意味着我们将讨论如何用C++编程语言来实现堆排序的过程。C++是面向对象的编程语言,具有丰富的库支持和高效的执行性能,是实现算法的理想选择。 描述"排序...

    C++中的几种排序算法

    C++中的几种排序算法 C++中的几种排序算法是计算机科学中的一种基本算法,用于对数据进行排序。排序算法的选择取决于具体的应用场景和数据特点。本文将介绍C++中的几种常见的排序算法,包括插入排序、选择排序、...

    C++实现各种排序算法.zip

    在这个压缩包中,"sort_algorithm_cpp-master"目录下可能包含了以下几种经典的排序算法的C++实现: 1. **冒泡排序(Bubble Sort)**:这是一种简单直观的排序算法,通过重复遍历待排序的数列,比较相邻元素并交换...

    C++常见的排序类

    在IT领域,排序算法是计算机科学中的基础且重要的部分,特别是在C++编程中。这个压缩包文件"Sort.cpp"显然包含了一些实现常见排序算法的C++类。让我们深入探讨一下这些排序算法及其在C++中的实现。 首先,我们来看...

    sort_algorithm_快速排序C++_

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的...

    排序问题C++MFC

    在C++中,最常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序以及堆排序等。每种排序算法都有其独特的优缺点,如时间复杂度、空间复杂度以及稳定性等。 1. 冒泡排序:是最简单的排序算法,通过...

    用C++实现各种排序算法

    本文将详细探讨在C++语言中实现的几种常见排序算法,包括快速排序、Shell排序、堆排序、折半排序、冒泡排序、归并排序以及B树的实现,并对直接排序法进行简要介绍。 1. **快速排序**:由C.A.R. Hoare提出的快速排序...

    c++算法入门学习

    首先,让我们从基础的排序算法开始。在C++中,我们有多种排序方法,如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序。这些排序算法各有优缺点,适用于不同的场景。例如,冒泡排序和选择排序虽然实现...

    C++ 就简单算法实现大全

    首先,你会接触到排序算法,如冒泡排序、选择排序、插入排序、快速排序和归并排序,这些算法用于对数据进行有效组织,提高数据检索效率。接下来,搜索算法,如线性搜索和二分搜索,将教会你如何在数据集中查找特定...

Global site tag (gtag.js) - Google Analytics