C++中 Sort函數(shù)詳細(xì)解析
前言
sort函數(shù)是algorithm庫(kù)下的一個(gè)函數(shù),sort函數(shù)是不穩(wěn)定的,即大小相同的元素在排序后相對(duì)順序可能發(fā)生改變,如果某些場(chǎng)景需要保持相同元素間的相對(duì)順序,可使用stable_sort
函數(shù),這里不過(guò)多介紹。
一、sort函數(shù)調(diào)用的兩種方式
默認(rèn): 兩個(gè)參數(shù)first
,last
,將[first, last)
區(qū)間內(nèi)元素升序排列。【注意區(qū)間為左閉右開(kāi)】
自定義排序: 需用戶(hù)指定排序規(guī)則Compare comp
,將 [first, last)
區(qū)間內(nèi)的元素按照用戶(hù)指定的順序排列。
二、sort函數(shù)使用場(chǎng)景
由于在排序過(guò)程中涉及到元素交換等操作,所以sort函數(shù)僅支持可隨機(jī)訪問(wèn)的容器,如數(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)用帶來(lái)過(guò)大的額外負(fù)荷,便會(huì)改用插入排序。而如果遞歸層次過(guò)深,有出現(xiàn)最壞情況的傾向,還會(huì)改用堆排序。
? 所以無(wú)論元素初始時(shí)為何種狀態(tài),sort()
的平均排序復(fù)雜度為均為O(N*log2(N)) ,具有不錯(cuò)的的性能,在刷算法題時(shí),可以直接使用sort()來(lái)對(duì)數(shù)據(jù)進(jìn)行排序,而不需手動(dòng)編寫(xiě)排序函數(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
類(lèi)型,即函數(shù)為 greater<int>()
; 如果是其他基本數(shù)據(jù)類(lèi)型如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
類(lèi)型, 例如:
bool cmp(int num1, int num2) { return num1 > num2; // 可以簡(jiǎn)單理解為 > 降序排列; < 升序排列 }
#include<iostream> #include<vector> #include<algorithm> using namespace std; bool cmp(int num1, int num2) { return num1 > num2; // 可以簡(jiǎn)單理解為 >: 降序排列; < : 升序排列 } 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)行比較,即誰(shuí)大誰(shuí)小。 基本數(shù)據(jù)類(lèi)型可直接進(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(); // 無(wú)參數(shù)構(gòu)造函數(shù) Student(string name, int grade) : name(name), grade(grade) {}; // 有參數(shù)構(gòu)造函數(shù) };
需求: 對(duì)一個(gè)班級(jí)內(nèi)的學(xué)生成績(jī)進(jìn)行排序,首先按成績(jī)進(jìn)行排序降序排列,若成績(jī)相同,則按照姓名字典順序升序排列。
自定義排序函數(shù);
bool cmp(Student s1, Student s2) { // 自定義排序 if (s1.grade != s2.grade) { // 如果學(xué)生成績(jī)不相同 return s1.grade > s2.grade; // 則按照成績(jī)降序排列 } 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(); // 無(wú)參數(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é)生成績(jī)不同 return s1.grade > s2.grade; // 則按照成績(jī)降序排列 } 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
類(lèi)型
- 若返回
true
,則表示num1
與num2
應(yīng)該交換順序; - 若返回
false
, 則num1
與num2
保持原有順序;
下面舉例說(shuō)明自定義比較函數(shù)的執(zhí)行過(guò)程:
對(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)過(guò)數(shù)次的比較與交換最終排序完成。
最終得到 5 4 3 2 1
到此這篇關(guān)于C++中 Sort函數(shù)詳細(xì)解析的文章就介紹到這了,更多相關(guān)C++ Sort函數(shù) 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++使用遞歸函數(shù)和棧操作逆序一個(gè)棧的算法示例
這篇文章主要介紹了C++使用遞歸函數(shù)和棧操作逆序一個(gè)棧的算法,結(jié)合實(shí)例形式分析了C++遞歸函數(shù)與逆序棧的相關(guān)操作技巧,需要的朋友可以參考下2017-05-05vscode?采用C++17版本進(jìn)行編譯的實(shí)現(xiàn)
本文主要介紹了vscode?采用C++17版本進(jìn)行編譯,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-01-01C語(yǔ)言十進(jìn)制轉(zhuǎn)二進(jìn)制代碼實(shí)例
這篇文章主要介紹了C語(yǔ)言十進(jìn)制轉(zhuǎn)二進(jìn)制代碼實(shí)例,并且轉(zhuǎn)換后會(huì)統(tǒng)計(jì)二進(jìn)制1的個(gè)數(shù),實(shí)例簡(jiǎn)單明了,需要的朋友可以參考下2014-06-06c++ 數(shù)字類(lèi)型和字符串類(lèi)型互轉(zhuǎn)詳解
今天小編就為大家分享一篇講解c++ 數(shù)字類(lèi)型和字符串類(lèi)型互轉(zhuǎn)的文章,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-09-09基于C語(yǔ)言編寫(xiě)一個(gè)多功能計(jì)算器
這篇文章主要為大家詳細(xì)介紹了如何基于C語(yǔ)言編寫(xiě)一個(gè)多功能計(jì)算器,除了四則混合運(yùn)算之外,還支持三角函數(shù)和絕對(duì)值等函數(shù),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-08-08