C++ stable_sort()
C++算法stable_sort()
C++算法 stable_sort()函数用于将[first，last)范围内的元素按升序排序类似于排序，但保持等效元素的顺序。
使用第一个版本的运算符 比较元素，第二个版本使用 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。
返回值
无
复杂度
运行时复杂度取决于可用内存量。
如果有足够的额外内存可用，则复杂度在首尾之间是线性的。最多执行N * log
2 (N)个元素比较，其中N = last-first。
如果没有可用的额外内存，则复杂度在first和last之间是多线性的持续。最多执行N * log
2
2 (N)个元素比较，其中N =倒数第一个。
数据竞争
在[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 )
