首页 > 编程笔记 > C++笔记 阅读：64

C++排序函数汇总（附带实例）

排序算法用于对容器内容进行多种方式的排序。C++ STL 中提供的常见排序算法如下表所示。

表：STL 的常见排序算法
函数 说明
sort(first, last) 将指定区间内的元素排序，默认为升序
stable_sort(first, last) 将指定区间内的元素排序，值相同的元素不改变位置
partial_sort(first, middle, last) 将 [first, last) 区间内的元素排序，排序后一部分放至 [first, middle) 区间，其余放至 [middle, last) 区间
partial_sort_copy(first, last, result_first, result_last) 将 [first, last) 区间内的元素排序，排序后存入 [result_first, result_last) 区间
is_sorted(first, last) 判断指定区间是否已经排好序（默认为升序）
merge(first, last, first2, last2, result) 把两个有序区间的元素合并，重新排序后放入 result 开始的序列

下面通过实例介绍 sort(first, last)、partial_sort(first, middle, last) 和 merge(first, last, first2, last2, result) 这三个模板函数的用法。

C++ sort(first,last)

该模板函数可将指定区间内的元素排序，只支持 array、vector、deque 这 3 类容器。函数原型如下： 
// 对指定区间内的元素排序，默认为升序排序
sort(first, last);
// 对指定区间内的元素排序，compare 为排序规则
sort(first, last, compare);

【实例 1】使用 sort() 函数，对数据进行递增排序，具体代码如下： 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void Output(int val) {          // 定义 Output() 函数
    cout << val << ' ';
}

int main() {
    vector<int> charVect;

    // 向集合中添加 6 个元素
    charVect.push_back('M');   // 77
    charVect.push_back('R');   // 82
    charVect.push_back('K');   // 75
    charVect.push_back('J');   // 74
    charVect.push_back('H');   // 72
    charVect.push_back('I');   // 73

    cout << "Vect : ";
    for_each(charVect.begin(), charVect.end(), Output);  // 输出排序前所有元素
    cout << endl;

    sort(charVect.begin(), charVect.end());               // 对集合中元素排序

    cout << "Vect : ";
    for_each(charVect.begin(), charVect.end(), Output);  // 输出排序后所有元素
    cout << endl;

    return 0;
}
运行结果为：

Vect : 77 82 75 74 72 73
Vect : 72 73 74 75 77 82

C++ partial_sort(first,middle,last)

该模板函数可将 (first,last) 区间的元素排序，排序后一部分元素放至 (first,middle) 区间内，其余元素放至 (middle,last) 区间内。

【实例 2】使用 partial_sort() 函数，将一周日期排序输出，具体代码如下： 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

void Output(const string& val) {   // 定义 Output() 函数
    cout << val << endl;
}

int main() {
    vector<string> strVect;

    // 向集合中添加 7 个元素
    strVect.push_back("Sunday");
    strVect.push_back("Monday");
    strVect.push_back("Tuesday");
    strVect.push_back("Wednesday");
    strVect.push_back("Thursday");
    strVect.push_back("Friday");
    strVect.push_back("Saturday");

    cout << "Vect : ";
    for_each(strVect.begin(), strVect.end(), Output);  // 输出原始顺序

    // 局部排序：仅将前 3 个最小元素排到最前面
    partial_sort(strVect.begin(), strVect.begin() + 3, strVect.end());

    cout << endl << "Vect : ";
    for_each(strVect.begin(), strVect.end(), Output);  // 输出排序后顺序
    return 0;
}
运行结果为： 
Vect : Sunday
Monday
Tuesday
Wednesday
Thursday
Friday
Saturday

Vect : Friday
Monday
Saturday
Wednesday
Tuesday
Thursday
Sunday
程序使用 partial_sort() 函数对 vector 容器内元素进行排序，将排序后的第 2~4 个元素放到容器的前一部分。

C++ merge(first,last,first2,last2,result)

该模板函数可把 (first,last) 区间和 (first2,last2) 区间的元素合并，重新排序后放至 result 开始的序列中。合并排序的前提是，两个待合并序列已排好序且排序规则相同，合并后默认仍使用该排序规则。

【实例 3】 使用 merge() 函数，将两个容器内的元素重新组合到另一个容器内，并输出，具体代码如下： 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

void Output(const string& val) {   // 定义 Output() 函数
    cout << val << endl;
}

int main() {
    vector<string> strVect1;
    vector<string> strVect2;

    // 向 strVect1 中添加 4 个元素
    strVect1.push_back("Sunday");
    strVect1.push_back("Monday");
    strVect1.push_back("Tuesday");
    strVect1.push_back("Wednesday");

    // 向 strVect2 中添加 4 个元素
    strVect2.push_back("Thursday");
    strVect2.push_back("Friday");
    strVect2.push_back("Saturday");
    strVect2.push_back("Over");

    cout << "Vect1 :" << endl;
    for_each(strVect1.begin(), strVect1.end(), Output);   // 输出 strVect1 所有元素

    cout << endl << "Vect2 :" << endl;
    for_each(strVect2.begin(), strVect2.end(), Output);   // 输出 strVect2 所有元素

    // 先分别排序
    sort(strVect1.begin(), strVect1.end());
    sort(strVect2.begin(), strVect2.end());

    // 合并两个有序区间到 strVect3
    int size = strVect1.size() + strVect2.size();
    vector<string> strVect3(size);

    merge(strVect1.begin(), strVect1.end(),
          strVect2.begin(), strVect2.end(),
          strVect3.begin());

    cout << endl << "Vect3 :" << endl;
    for_each(strVect3.begin(), strVect3.end(), Output);   // 输出合并后的所有元素

    return 0;
}
运行结果为：

Vect1 :
Sunday
Monday
Tuesday
Wednesday

Vect2 :
Thursday
Friday
Saturday
Over

Vect3 :
Friday
Monday
Over
Saturday
Sunday
Thursday
Tuesday
Wednesday

程序使用 merge() 函数将两个容器（strVect1 和 strVect2）内的元素重新排列，组合到另一个容器（strVect3）内。

相关文章