极客笔记C++ 算法 稳定排序(stable_sort())
C++算法 稳定排序(stable_sort()) 函数用于将范围[first, last)中的元素按升序排序，但保持等效元素的顺序。
第一种版本使用< strong>小于(<)操作符进行比较，第二种版本使用< strong>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*log2(N)次元素比较，其中N = last – first。
如果没有额外内存可用，则复杂度与first和last之间的距离成多项式关系。执行N*log2^2(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 )