e <functional>
using namespace std;
void MyPrint(int val){ cout << val << " "; }
int main(int argc, char* argv[])
{
// 从小到大排序
int iArray[] = { 56, 43, 22, 1, 34, 7, 89, 0, 43, 56 };
const int len = sizeof(iArray) / sizeof(int);
sort(iArray, iArray + len);
for_each(iArray, iArray + len, [](int val){cout << val << " "; });
cout << endl;
// 从大到小排序
vector<int> var = { 45, 76, 33, 21, 7, 89, 0, 34, 5, 7 };
sort(var.begin(), var.end(), greater<int>());
for_each(var.begin(), var.end(), MyPrint);
system("pause");
return 0;
}
9.4 稳定排序算法
Stable_sort 算法函数,用于对序列进行稳定排序。stable_sort的用法如下:
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
其中,first、last
是随机访问迭代器,表示待排序的序列的范围。stable_sort函数将[first, last]
范围内的元素按照递增顺序排序,并保证相等元素的相对顺序不变,将排序后的结果存储在相同的容器中。
stable_sort函数使用的是归并排序算法,具有良好的稳定性,可以保证相等元素的相对顺序不变。在实现排序功能前,stable_sort
函数首先将序列从中间分成两个子序列,然后分别对两个子序列进行排序,最后归并两个排序好的子序列,形成一个完整的排序序列。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Student{
int id;
char *name;
int score;
Student(int _id, char* _name, int _score)
{
id = _id; name = _name; score = _score;
}
};
void MyPrint(Student val)
{
cout << val.id << val.name << val.score << endl;
}
bool CompByScore(Student x, Student y)
{
// 按照学生的成绩从小到大进行排序
return x.score < y.score ? 1 : 0;
}
int main(int argc, char* argv[])
{
vector<Student> var;
var.push_back(Student(1, "keey", 90));
var.push_back(Student(2, "marry", 82));
var.push_back(Student(3, "lisa", 70));
stable_sort(var.begin(), var.end(), CompByScore);
for_each(var.begin(), var.end(), MyPrint);
system("pause");
return 0;
}
9.5 容器归并算法
Merge 算法函数,用于将两个已排序的序列合并成一个有序序列。merge的用法如下:
template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
其中,first1、last1、first2、last2
是输入迭代器,表示待合并的两个已排序序列的范围;result
是输出迭代器,表示合并后的有序序列的目标位置。merge
函数将已排序的两个序列按照递增顺序合并成一个新的有序序列,输出到result
所指向的迭代器位置,并将输出结果的尾后迭代器作为函数的返回值返回。
merge函数使用的是归并排序算法,在实现合并功能前,merge函数首先将输入序列分成若干个小的段,将不同段之间的元素合并成一个有序段,然后再将合并后的所有段依次合并,完成最终的排序结果。
该算法可以实现将两个具有相同升降方向的有序序列(必须有序),合并成另一个有序序列。
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
void MyPrint(int val){ cout << val << " "; }
int main(int argc, char* argv[])
{
// 按照升序方式将两个序列合并
int iArray1[3] = { 1, 2, 3 };
int iArray2[7] = { 4, 5, 6, 7, 8, 9, 10 };
int result[10];
merge(iArray1, iArray1 + 3, iArray2, iArray2 + 7, result);
for_each(result, result + 10, MyPrint);
cout << endl;
// 按照降序方式将两个序列合并
int iArray3[5] = { 30, 20, 15, 9, 2 };
int iArray4[4] = { 10, 5, 3, 1 };
int result2[9];
merge(iArray3, iArray3 + 5, iArray4, iArray4 + 4, result2, greater<int>());
for_each(result2, result2 + 9, MyPrint);
cout << endl;
// 内部归并排序,这里只给出降序排列代码,升序排列与第一个案例相同
int iArray5[] = { 100, 80, 60, 40, 20, 10, 90, 70, 50, 30 };
const int len = sizeof(iArray5) / sizeof(int); // 数组元素总长度
int middle = 6; // 选择一个切割中位数下标
inplace_merge(iArray5, iArray