快捷導(dǎo)航

C++中 Sort函數(shù)詳細(xì)解析

更新時(shí)間：2022年08月18日 16:29:08 作者：zhangbw~

這篇文章主要介紹了C++中 Sort函數(shù)詳細(xì)解析，sort函數(shù)是algorithm庫下的一個(gè)函數(shù)，sort函數(shù)是不穩(wěn)定的，即大小相同的元素在排序后相對(duì)順序可能發(fā)生改變

前言

sort函數(shù)是algorithm庫下的一個(gè)函數(shù)，sort函數(shù)是不穩(wěn)定的，即大小相同的元素在排序后相對(duì)順序可能發(fā)生改變，如果某些場景需要保持相同元素間的相對(duì)順序，可使用stable_sort函數(shù)，這里不過多介紹。

一、sort函數(shù)調(diào)用的兩種方式

默認(rèn): 兩個(gè)參數(shù)first,last，將[first, last)區(qū)間內(nèi)元素升序排列。【注意區(qū)間為左閉右開】

自定義排序: 需用戶指定排序規(guī)則Compare comp,將 [first, last)區(qū)間內(nèi)的元素按照用戶指定的順序排列。

二、sort函數(shù)使用場景

由于在排序過程中涉及到元素交換等操作，所以sort函數(shù)僅支持可隨機(jī)訪問的容器，如數(shù)組， string、vector、deque等。

三、sort函數(shù)排序原理

? sort()并非只是普通的快速排序，除了對(duì)普通的快速排序進(jìn)行優(yōu)化，它還結(jié)合了插入排序和堆排序。根據(jù)不同的數(shù)量級(jí)別以及不同情況，能自動(dòng)選用合適的排序方法。當(dāng)數(shù)據(jù)量較大時(shí)采用快速排序，分段遞歸。一旦分段后的數(shù)據(jù)量小于某個(gè)閥值，為避免遞歸調(diào)用帶來過大的額外負(fù)荷，便會(huì)改用插入排序。而如果遞歸層次過深，有出現(xiàn)最壞情況的傾向，還會(huì)改用堆排序。

? 所以無論元素初始時(shí)為何種狀態(tài)，sort()的平均排序復(fù)雜度為均為O(N*log2(N)) ，具有不錯(cuò)的的性能，在刷算法題時(shí)，可以直接使用sort()來對(duì)數(shù)據(jù)進(jìn)行排序，而不需手動(dòng)編寫排序函數(shù)。

四、sort函數(shù)使用案例

1.升序排列

sort函數(shù)如果不傳入第三個(gè)參數(shù)，則默認(rèn)是升序排列。

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

using namespace std;

int main() {
    // 方式一、使用數(shù)組
    int a[10] = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(a, a + 10);  // 10為元素個(gè)數(shù)

    for (int i = 0; i < 10; i++) cout << a[i] << ' ';		// 輸出排序后數(shù)組
    cout << endl;

    // 方式二、使用 vector
    vector<int> arr = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(arr.begin(), arr.end());  // 10為元素個(gè)數(shù)
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';	// 輸出排序后數(shù)組

    return 0;
}

2.降序排列

實(shí)現(xiàn)方式1

實(shí)現(xiàn)降序排列，需傳入第三個(gè)參數(shù)–比較函數(shù)，greater<type>()，這里的元素為int 類型，即函數(shù)為 greater<int>(); 如果是其他基本數(shù)據(jù)類型如float、double、long等也是同理。

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

using namespace std;

int main() {
    // 方式一、使用數(shù)組
    int a[10] = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(a, a + 10, greater<int>());  // 10為元素個(gè)數(shù)

    for (int i = 0; i < 10; i++) cout << a[i] << ' ';		// 輸出排序后數(shù)組
    cout << endl;	// 輸出 9 8 7 6 5 4 3 2 1 0 

    // 方式二、使用 vector
    vector<int> arr = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(arr.begin(), arr.end(), greater<int>()); 
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';	// 輸出排序后數(shù)組

    return 0;
}

實(shí)現(xiàn)方式2

我們也可以使用自定義的比較函數(shù)，函數(shù)的返回值為bool類型， 例如：

bool cmp(int num1, int num2) {
    return num1 > num2;     // 可以簡單理解為 > 降序排列;  <  升序排列
}

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

using namespace std;

bool cmp(int num1, int num2) {
    return num1 > num2;     // 可以簡單理解為 >： 降序排列;  < ： 升序排列
}

int main() {
    // 一、使用數(shù)組
    int a[10] = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(a, a + 10, cmp);  // 使用自定義排序函數(shù)

    for (int i = 0; i < 10; i++) cout << a[i] << ' ';		// 輸出排序后數(shù)組
    cout << endl;	// 輸出 9 8 7 6 5 4 3 2 1 0 

    // 二、使用 vector
    vector<int> arr = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(arr.begin(), arr.end(), cmp);   // 使用自定義排序函數(shù)
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';	// 輸出排序后數(shù)組

    return 0;
}

3.結(jié)構(gòu)體排序(自定義比較函數(shù))

? 要對(duì)元素進(jìn)行排序，前提是元素之間可以進(jìn)行比較，即誰大誰小。基本數(shù)據(jù)類型可直接進(jìn)行大小比較，但結(jié)構(gòu)體元素之間的大小關(guān)系需要我們自己指定，如果不指定，則結(jié)構(gòu)體之間大小關(guān)系就不確定，則不能夠排序。

結(jié)構(gòu)體排序案例1: 對(duì)學(xué)生信息進(jìn)行排序

學(xué)生有姓名，分?jǐn)?shù)兩個(gè)屬性,

struct Student {    // 學(xué)生結(jié)構(gòu)體
    string name;    // 學(xué)生姓名
    int grade;      // 學(xué)生分?jǐn)?shù)
    Student();  // 無參數(shù)構(gòu)造函數(shù)
    Student(string name, int grade) : name(name), grade(grade) {};  // 有參數(shù)構(gòu)造函數(shù)
};

需求： 對(duì)一個(gè)班級(jí)內(nèi)的學(xué)生成績進(jìn)行排序，首先按成績進(jìn)行排序降序排列，若成績相同，則按照姓名字典順序升序排列。

自定義排序函數(shù);

bool cmp(Student s1, Student s2) {  // 自定義排序
    if (s1.grade != s2.grade) {     // 如果學(xué)生成績不相同
        return s1.grade > s2.grade; // 則按照成績降序排列
    }
    return s1.name < s2.name;   // 否則按照姓名升序排列
}

排序代碼:

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

using namespace std;

struct Student {    // 學(xué)生結(jié)構(gòu)體
    string name;    // 學(xué)生姓名
    int grade;      // 學(xué)生分?jǐn)?shù)
    Student();  // 無參數(shù)構(gòu)造函數(shù)
    Student(string name, int grade) : name(name), grade(grade) {};  // 有參數(shù)構(gòu)造函數(shù)
};

bool cmp(Student s1, Student s2) {  // 自定義排序
    if (s1.grade != s2.grade) {     // 如果學(xué)生成績不同
        return s1.grade > s2.grade; // 則按照成績降序排列
    }
    return s1.name < s2.name;   // 否則按照姓名升序排列
}

int main() {
    vector<Student> studs;
    studs.emplace_back("Bob", 80);
    studs.emplace_back("Ali", 90);
    studs.emplace_back("Ann", 85);
    studs.emplace_back("Liming", 90);
    studs.emplace_back("Trump", 79);
    studs.emplace_back("Fury", 58);
    studs.emplace_back("Jam", 62);
    studs.emplace_back("Lucy", 89);

    sort(studs.begin(), studs.end(), cmp);  // 排序
    for (int i = 0; i < studs.size(); i++) {    // 輸出結(jié)果
        cout << studs[i].name << "\t" << studs[i].grade << endl;
    }
    return 0;
}

五、自定義comp函數(shù)返回true或false作用

bool cmp(int num1, int num2) {	// 實(shí)現(xiàn)降序排列
    return num1 > num2;	// num1大于num2時(shí)返回true，否則返回false
}

自定義函數(shù)返回值為bool類型

若返回true，則表示num1 與num2應(yīng)該交換順序；
若返回false, 則num1 與num2 保持原有順序；

下面舉例說明自定義比較函數(shù)的執(zhí)行過程:

對(duì) 2, 5, 1, 3, 4 降序排列
調(diào)用cmp函數(shù)時(shí)，將5賦值給num1, 2賦值給num2 (注意順序)
5 > 2, 返回true，num1 與 num2需進(jìn)行交換；即5應(yīng)該在2的前面
數(shù)組變?yōu)? 5, 2, 1, 3, 4

第二次將3賦值給num1, 1賦值給num2，
3 > 1, 返回true，num1 與 num2需進(jìn)行交換；即3應(yīng)該在1的前面
數(shù)組變?yōu)? 5, 2, 3, 1, 4

之后經(jīng)過數(shù)次的比較與交換最終排序完成。
最終得到 5 4 3 2 1