C++ 算法 sort()

2024年8月30日 | 阅读4分钟

C++ 算法 sort() 函数用于将范围 [first, last) 内的元素按升序排序。

第一个版本使用运算符 < 比较元素，第二个版本使用 comp 比较元素。

语法

default (1)	
	template <class RandomAccessIterator>
  	void sort (RandomAccessIterator first, RandomAccessIterator last);

custom (2)	
	template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

参数

first：指向要排序范围内的第一个元素的随机访问迭代器。

last：指向要排序范围内的最后一个元素之后一个位置的随机访问迭代器。

comp：一个用户定义的二元谓词函数，接受两个参数，如果这两个参数有序则返回true，否则返回false。它遵循严格的弱排序来对元素进行排序。

返回值

无

复杂度

排序的平均复杂度为 N*log₂ (N)，其中 N = last - first。

数据竞争

范围 [first, last) 中的对象被修改。

异常

如果任何元素比较、元素交换或迭代器上的操作抛出异常，此函数将抛出异常。

注意：无效参数会导致未定义行为。

示例 1

让我们看一个简单的例子来演示 sort() 的用法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  vector<int> v = {3, 1, 4, 2, 5};
  
    cout<<"Before sorting: ";
    for_each(v.begin(), v.end(), [](int x) {
    cout << x << " ";
  });

  sort(v.begin(), v.end());
  
  cout<<"\nAfter sorting:  ";
  for_each(v.begin(), v.end(), [](int x) {
    cout << x << " ";
  });
  
  return 0;
}

输出

Before sorting: 3 1 4 2 5 
After sorting:  1 2 3 4 5

示例 2

让我们看另一个简单示例

#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector

using namespace std;

bool myfunction (int i,int j) { return (i<j); }

struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
  int myints[] = {32,71,12,45,26,80,53,33};
  vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

  // using default comparison (operator <):
  sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // print out content:
  cout << "myvector contains:";
  for (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    cout << ' ' << *it;
  cout << '\n';

  return 0;
}

输出

myvector contains: 12 26 32 33 45 53 71 80

示例 3

让我们看另一个简单示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;
 
void print(const vector <std::string>& v)
{
    vector <string>::const_iterator i;
    for(i = v.begin(); i != v.end(); i++)
    {
        cout << *i << "    ";
    }
    cout << endl;
}
 
int main()
{
    vector <string> v;
    // Push functional programming languages
    v.push_back("Lisp");
    v.push_back("C#");
    v.push_back("Java");
    v.push_back("Python");
    v.push_back("C++");
    v.push_back("Pascal");
    v.push_back("Sql");
 
    // sort without predicate
    sort(v.begin(), v.end());
    cout << "Sorted list of functional programming languages - " << endl;
    print(v);
    // sort with predicate
    sort(v.begin(), v.end(), std::greater<std::string>());
    cout << "Reverse Sorted list of functional programming languages - " << endl;
    print(v);
}

输出

Sorted list of functional programming languages - 
C#    C++    Java    Lisp    Pascal    Python    Sql    
Reverse Sorted list of functional programming languages - 
Sql    Python    Pascal    Lisp    Java    C++    C#

示例 4

让我们看另一个简单示例

#include <vector>
#include <algorithm>
#include <functional>     
#include <iostream>
 
using namespace std;
 
// return whether first element is greater than the second
bool userdefgreater(int elem1, int elem2)
{    return elem1 > elem2;    }
 
int main()
{
  vector <int> vec1;  // container
  vector <int>::iterator Iter1;  // iterator
  int k;
  for (k = 0; k <= 15; k++)
    vec1.push_back(k);
  random_shuffle(vec1.begin(), vec1.end());
  cout <<"Original random shuffle vector vec1 data:\n";
  for (Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)
    cout <<*Iter1<<" ";
  cout <<endl;
  sort(vec1.begin(), vec1.end());
  cout <<"\nSorted vector vec1 data:\n";
  for (Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)
    cout <<*Iter1<<" ";
  cout <<endl;
  // to sort in descending order, specify binary predicate
  sort(vec1.begin(), vec1.end(), greater<int>());
  cout <<"\nRe sorted (greater) vector vec1 data:\n";
  for (Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)
    cout <<*Iter1<<" ";
  cout <<endl;
  // a user-defined binary predicate can also be used
  sort(vec1.begin(), vec1.end(), userdefgreater);
  cout <<"\nUser defined re sorted vector vec1 data:\n";
  for (Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)
    cout <<*Iter1<<" ";
  cout <<endl;

  return 0;
}

输出

Original random shuffle vector vec1 data:
4 10 11 15 14 5 13 1 6 9 3 7 8 2 0 12 

Sorted vector vec1 data:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

Re sorted (greater) vector vec1 data:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

User defined re sorted vector vec1 data:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

下一主题C++ 算法

C++ 算法 sort()

语法

参数

返回值

复杂度

数据竞争

异常

注意：无效参数会导致未定义行为。

示例 1

示例 2

示例 3

示例 4

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 算法 sort()

语法

参数

返回值

复杂度

数据竞争

异常

注意：无效参数会导致未定义行为。

示例 1

示例 2

示例 3

示例 4

相关帖子

algorithm all_of() 函数

algorithm any_of() 函数

algorithm is_sorted_until() 函数

algorithm equal() 函数

algorithm count_if() 函数

algorithm partition() 函数

algorithm reverse_copy() 函数

algorithm find() 函数

algorithm merge() 函数