c++ - C++ 中的排序函数如何工作?

标签 c++ sorting

<分区>

在下面的代码中,sort() 函数是如何工作的? 例如,如果我们有一个数组:

a [5] = {1,2,3,4,5};

然后我使用 bool cmp() 函数将其降序排列, 我想知道:它是如何工作的,哪个元素是 int a 哪个是 int b (bool cmp() 中的参数函数),它什么时候排序,bool cmp() 什么时候返回 1,什么时候返回 0?

#include <iostream>
#include <algorithm>

using namespace std;
bool cmp (int a , int b)
{
    return (a > b );
}

int main ()
{
    int a[100];
    int n;
    cin >> n;
    for (int i=0 ; i<n ;i++)
        cin >> a[i];

    sort(a,a+n,cmp);
    cout << endl << endl;
    for (int i=0 ; i<n ;i++)
        cout << a[i] << " ";



    return 0;
}

最佳答案

如何实现取决于标准库的实现。它保证有 O(Nlog(N))复杂。常见的实现使用 quicksortintrosort .

比较函数是一个二元函数,必须返回true如果第一个参数严格小于第二个参数。该实现使用此函数比较容器的两个元素以确定哪个元素应该在哪个元素之前 - 所以 ab可以是容器中的任意两个元素。此函数必须对元素进行严格的弱排序。即:

  • 元素永远不会小于自身
  • 如果x < y , 那么 y < x 就不是这样了
  • 如果x < yy < z , 然后 x < z

如果您不提供比较函数,operator<用来。同样,您可以传递 std::less作为比较函数。

关于c++ - C++ 中的排序函数如何工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14689215/

相关文章:

c++ - MPI_Isend/Recv-是否存在死锁?

c++ - 在 C++ 项目中使用 tinyXml2

c++ - 清理多个 if 语句 C++

c++ - 不相关类型之间的 reinterpret_cast 和 virtual

Java:使用比较器和属性的第二个字对对象列表进行排序

c - 函数不适用于 C 程序选择排序

c++ - 如何在 C++ 中确定一组映射中的整数?

PHP 使用 ORDER BY 查询 MySQL 对数据库项目进行排序

algorithm - 对只有 3 个元素的 int 数组进行排序

sorting - 选择行并在 R 中对结果进行排序