C++ Sort函數詳解

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

成都創(chuàng)新互聯主營椒江網站建設的網絡公司,主營網站建設方案,成都APP應用開發(fā),椒江h(huán)5成都微信小程序搭建,椒江網站營銷推廣歡迎椒江等地區(qū)企業(yè)咨詢

一、sort函數調用的兩種方式

方式一(默認)	void sort (RandomAccessIterator first, RandomAccessIterator last);
方式二(自定義)	void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

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

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

二、sort函數使用場景

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

三、sort函數排序原理

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

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

四、sort函數使用案例 1.升序排列

sort函數如果不傳入第三個參數，則默認是升序排列。

#include#include#include

using namespace std;

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

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

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

    return 0;
}

2.降序排列

• 實現方式1

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

#include#include#include

using namespace std;

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

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

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

    return 0;
}

• 實現方式2

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

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

#include#include#include

using namespace std;

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

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

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

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

    return 0;
}

3.結構體排序(自定義比較函數)

? 要對元素進行排序，前提是元素之間可以進行比較，即誰大誰小。 基本數據類型可直接進行大小比較， 但結構體元素之間的大小關系需要我們自己指定，如果不指定，則結構體之間大小關系就不確定，則不能夠排序。

結構體排序案例1: 對學生信息進行排序

學生有姓名，分數兩個屬性,

struct Student {// 學生結構體
    string name;    // 學生姓名
    int grade;      // 學生分數
    Student();  // 無參數構造函數
    Student(string name, int grade) : name(name), grade(grade) {};  // 有參數構造函數
};

需求： 對一個班級內的學生成績進行排序，首先按成績進行排序降序排列，若成績相同，則按照姓名字典順序升序排列。

• 自定義排序函數

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

• 排序代碼

#include#include#include

using namespace std;

struct Student {// 學生結構體
    string name;    // 學生姓名
    int grade;      // 學生分數
    Student();  // 無參數構造函數
    Student(string name, int grade) : name(name), grade(grade) {};  // 有參數構造函數
};

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

int main() {vectorstuds;
    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++) {// 輸出結果
        cout<< studs[i].name<< "\t"<< studs[i].grade<< endl;
    }
    return 0;
}

五、自定義comp函數返回true或false作用

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

自定義函數返回值為bool類型

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

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

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

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

之后經過數次的比較與交換最終排序完成。
最終得到 5 4 3 2 1

六、參考文章鏈接

https://www.cplusplus.com/reference/algorithm/sort/

https://blog.csdn.net/qq_41575507/article/details/105936466

胡凡算法筆記

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站名稱：C++Sort函數詳解-創(chuàng)新互聯
鏈接地址：http://chinadenli.net/article34/cdodse.html

成都網站建設公司_創(chuàng)新互聯，為您提供面包屑導航、動態(tài)網站、網站收錄、軟件開發(fā)、關鍵詞優(yōu)化、響應式網站

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯