C++ 算法 stable_sort()

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

C++ 算法 stable_sort() 函数用于将范围 [first, last) 中的元素按升序排序，与 sort 类似，但保持等价元素的相对顺序。

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

语法

template <class RandomAccessIterator>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp );

参数

first：一个双向迭代器，指向要排序范围中的第一个元素。

last：一个双向迭代器，指向要排序范围中最后一个元素的后一个位置。

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

返回值

无

复杂度

运行时复杂度取决于可用内存量。

如果有足够的额外内存可用，则复杂度与 first 和 last 之间的距离呈线性关系。执行的元素比较次数最多为 N*log₂(N)，其中 N = last - first。

如果没有额外内存可用，则复杂度与 first 和 last 之间的距离呈多线性关系。执行的元素比较次数最多为 N*log₂²(N)，其中 N = last - first。

数据竞争

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

异常

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

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

示例 1

让我们看一个简单的例子来演示 stable_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 << " ";
  });

  stable_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 <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
struct Employee {
    Employee(int age, string name) : age(age), name(name) { } 
    int age;
    string name;  // Does not particpate in comparisons
};
 
bool operator<(const Employee &lhs, const Employee &rhs) {
    return lhs.age < rhs.age;
}
 
int main()
{
    vector<Employee> v = { 
        Employee(58, "Robin"),
        Employee(23, "Bob"),
        Employee(60, "Devid"),
    };  
 
    stable_sort(v.begin(), v.end());
    
    cout<<"Age : Name "<<endl<<"-----------\n";
    for (const Employee &e : v) {
        cout << e.age << " : " << e.name << '\n';
    }
    
    return 0;
}

输出

Age : Name 
-----------
23 : Bob
58 : Robin
60 : Devid

示例 3

让我们看另一个简单示例

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

using namespace std;
 
struct Student {
    string name;
    int sec;
    char group;
};
 
bool compBySec(Student a, Student b)
{
    return a.sec < b.sec;
}
 
bool compByGroup(Student a, Student b)
{
    return a.group < b.group;
}
 
bool compByName(Student a, Student b)
{
    return a.name < b.name;
}
 
void print(const vector <Student>& v)
{
    cout << "Name  \tSec\tGroup" << "\n-------------------------"<<endl;
    for (unsigned int i = 0; i < v.size(); i++)
    {   
        cout << v[i].name << "\t" << v[i].sec<< "\t"
                  << v[i].group << endl;
    }
}
 
int main()
{
    vector <Student> Students;
    string name[] = {"Anjali", "Bob", "Chinu  ", "Faizal ",
                          "Nikita ", "Deep ", "Aman", "Rohit "};
    int sec[] = {3, 4, 3, 3, 1, 4, 3, 2};
    int group[] = {'A', 'C', 'A', 'A', 'A', 'B', 'B', 'A'};
 
    for (int i = 0; i < 8; i++)
    {
        Student p;   
        p.name =  name[i];
        p.sec = sec[i];
        p.group = group[i];
        Students.push_back(p);
    }
    stable_sort(Students.begin(), Students.end(), compByName);
    cout << "Stable Sort by name" << endl;
    print(Students);
    cout << endl;
    stable_sort(Students.begin(), Students.end(), compBySec);
    cout << "Stable Sort by section" << endl;
    print(Students);
    
    return 0;
}

输出

Stable Sort by name
Name  	Sec	Group
-------------------------
Aman	3	B
Anjali	3	A
Bob	4	C
Chinu  	3	A
Deep 	4	B
Faizal 	3	A
Nikita 	1	A
Rohit 	2	A

Stable Sort by section
Name  	Sec	Group
-------------------------
Nikita 	1	A
Rohit 	2	A
Aman	3	B
Anjali	3	A
Chinu  	3	A
Faizal 	3	A
Bob	4	C
Deep 	4	B

示例 4

让我们看另一个简单示例

#include <vector>  
#include <algorithm>  
#include <functional>      // For greater<int>( )  
#include <iostream>  
  
// Return whether first element is greater than the second  
bool UDgreater (int elem1, int elem2 )  
{  
   return elem1 > elem2;  
}  
  
int main( )  
{  
   using namespace std;  
   vector <int> v1;  
   vector <int>::iterator Iter1;  
  
   int i;  
   for ( i = 0 ; i <= 5 ; i++ )  
   {  
      v1.push_back( 2 * i );  
   }  
  
   for ( i = 0 ; i <= 5 ; i++ )  
   {  
      v1.push_back( 2 * i  );  
   }  
  
   cout << "Original vector v1 = ( " ;  
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )  
      cout << *Iter1 << " ";  
   cout << ")" << endl;  
  
   stable_sort(v1.begin( ), v1.end( ) );  
   cout << "Sorted vector v1 = ( " ;  
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )  
      cout << *Iter1 << " ";  
   cout << ")" << endl;  
  
   // To sort in descending order, specify binary predicate  
   stable_sort(v1.begin( ), v1.end( ), greater<int>( ) );  
   cout << "Resorted (greater) vector v1 = ( " ;  
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )  
      cout << *Iter1 << " ";  
   cout << ")" << endl;  
  
   // A user-defined (UD) binary predicate can also be used  
   stable_sort(v1.begin( ), v1.end( ), UDgreater );  
   cout << "Resorted (UDgreater) vector v1 = ( " ;  
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )  
      cout << *Iter1 << " ";  
   cout << ")" << endl;  
   
   return 0;
}

输出

Original vector v1 = ( 0 2 4 6 8 10 0 2 4 6 8 10 )
Sorted vector v1 = ( 0 0 2 2 4 4 6 6 8 8 10 10 )
Resorted (greater) vector v1 = ( 10 10 8 8 6 6 4 4 2 2 0 0 )
Resorted (UDgreater) vector v1 = ( 10 10 8 8 6 6 4 4 2 2 0 0 )

下一主题C++ 算法

C++ 算法 stable_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++ 算法 stable_sort()

语法

参数

返回值

复杂度

数据竞争

异常

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

示例 1

示例 2

示例 3

示例 4

相关帖子

algorithm count() 函数

algorithm sort() 函数

C++ Thread hardware_concurrency() 函数

algorithm all_of() 函数

algorithm any_of() 函数

algorithm find_first_of() 函数

algorithm find_end() 函数

algorithm generate_n() 函数

algorithm reverse_copy() 函数