C++中 Sort函數(shù)詳細解析
前言
sort函數(shù)是algorithm庫下的一個函數(shù)，sort函數(shù)是不穩(wěn)定的，即大小相同的元素在排序后相對順序可能發(fā)生改變，如果某些場景需要保持相同元素間的相對順序，可使用stable_sort函數(shù)，這里不過多介紹。
一、sort函數(shù)調(diào)用的兩種方式
默認(rèn): 兩個參數(shù)first,last，將[first, last)區(qū)間內(nèi)元素升序排列。【注意區(qū)間為左閉右開】
自定義排序: 需用戶指定排序規(guī)則Compare comp,將 [first, last)區(qū)間內(nèi)的元素按照用戶指定的順序排列。
二、sort函數(shù)使用場景
由于在排序過程中涉及到元素交換等操作，所以sort函數(shù)僅支持可隨機訪問的容器，如數(shù)組， string、vector、deque等。
三、sort函數(shù)排序原理
? sort()并非只是普通的快速排序，除了對普通的快速排序進行優(yōu)化，它還結(jié)合了插入排序和堆排序。根據(jù)不同的數(shù)量級別以及不同情況，能自動選用合適的排序方法。當(dāng)數(shù)據(jù)量較大時采用快速排序，分段遞歸。一旦分段后的數(shù)據(jù)量小于某個閥值，為避免遞歸調(diào)用帶來過大的額外負荷，便會改用插入排序。而如果遞歸層次過深，有出現(xiàn)最壞情況的傾向，還會改用堆排序。
? 所以無論元素初始時為何種狀態(tài)，sort()的平均排序復(fù)雜度為均為O(N*log2(N)) ，具有不錯的的性能，在刷算法題時，可以直接使用sort()來對數(shù)據(jù)進行排序，而不需手動編寫排序函數(shù)。
四、sort函數(shù)使用案例
1.升序排列
sort函數(shù)如果不傳入第三個參數(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為元素個數(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為元素個數(shù)
for (int i = 0; i < 10; i++) cout << arr[i] << ' '; // 輸出排序后數(shù)組
return 0;
}
2.降序排列
實現(xiàn)方式1
實現(xiàn)降序排列，需傳入第三個參數(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為元素個數(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;
}實現(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ù))
? 要對元素進行排序，前提是元素之間可以進行比較，即誰大誰小。 基本數(shù)據(jù)類型可直接進行大小比較， 但結(jié)構(gòu)體元素之間的大小關(guān)系需要我們自己指定，如果不指定，則結(jié)構(gòu)體之間大小關(guān)系就不確定，則不能夠排序。
結(jié)構(gòu)體排序案例1: 對學(xué)生信息進行排序
學(xué)生有姓名，分?jǐn)?shù)兩個屬性,
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ù)
};需求： 對一個班級內(nèi)的學(xué)生成績進行排序，首先按成績進行排序降序排列，若成績相同，則按照姓名字典順序升序排列。
自定義排序函數(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) { // 實現(xiàn)降序排列
return num1 > num2; // num1大于num2時返回true，否則返回false
}自定義函數(shù)返回值為bool類型
- 若返回
true，則表示num1與num2應(yīng)該交換順序； - 若返回
false, 則num1與num2保持原有順序；
下面舉例說明自定義比較函數(shù)的執(zhí)行過程:
對 2, 5, 1, 3, 4 降序排列
調(diào)用cmp函數(shù)時，將5賦值給num1, 2賦值給num2 (注意順序)
5 > 2, 返回true，num1 與 num2需進行交換；即5應(yīng)該在2的前面
數(shù)組變?yōu)? 5, 2, 1, 3, 4第二次 將3賦值給num1, 1賦值給num2，
3 > 1, 返回true，num1 與 num2需進行交換；即3應(yīng)該在1的前面
數(shù)組變?yōu)? 5, 2, 3, 1, 4之后經(jīng)過數(shù)次的比較與交換最終排序完成。
最終得到 5 4 3 2 1
到此這篇關(guān)于C++中 Sort函數(shù)詳細解析的文章就介紹到這了,更多相關(guān)C++ Sort函數(shù) 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++ vector刪除符合條件的元素示例,需要的朋友可以參考下2014-02-02
這篇文章主要介紹了C++11/14的新特性(更簡潔)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-01-01
這篇文章主要介紹了C++使用遞歸函數(shù)和棧操作逆序一個棧的算法,結(jié)合實例形式分析了C++遞歸函數(shù)與逆序棧的相關(guān)操作技巧,需要的朋友可以參考下2017-05-05
求余運算符“%”，二元運算符，具有左結(jié)合性。參與運算的量均為整型。求余運算的結(jié)果等于兩個數(shù)相除后的余數(shù)?？此坪芎唵蔚倪\算符，卻也真要掌握用好它也不容易，這篇文章主要介紹了C++中求余運算符(%)的相關(guān)資料,需要的朋友可以參考借鑒，下面來一起看看吧。2017-01-01
本文主要介紹了vscode?采用C++17版本進行編譯，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要介紹了C語言十進制轉(zhuǎn)二進制代碼實例,并且轉(zhuǎn)換后會統(tǒng)計二進制1的個數(shù),實例簡單明了,需要的朋友可以參考下2014-06-06
這篇文章主要介紹了C++與C語言常用的語法對比，文章基于c++和C語言的相關(guān)資料展開兩者的語法相互對比，需要的小伙伴可以參考一下，希望對你的學(xué)習(xí)有所幫助2022-04-04
c++ 數(shù)字類型和字符串類型互轉(zhuǎn)詳解
今天小編就為大家分享一篇講解c++ 數(shù)字類型和字符串類型互轉(zhuǎn)的文章，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-09-09
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)輪廓外接多邊形，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要為大家詳細介紹了如何基于C語言編寫一個多功能計算器，除了四則混合運算之外，還支持三角函數(shù)和絕對值等函數(shù)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-08-08