C++ Sort函數(shù)使用場景分析
C++ Sort函數(shù)詳解
前言 ：sort函數(shù)是algorithm庫下的一個函數(shù)，sort函數(shù)是不穩(wěn)定的，即大小相同的元素在排序后相對順序可能發(fā)生改變，如果某些場景需要保持相同元素間的相對順序，可使用
stable_sort函數(shù)，這里不過多介紹。
一、sort函數(shù)調(diào)用的兩種方式
| 方式一(默認(rèn)) | void sort (RandomAccessIterator first, RandomAccessIterator last); |
|---|---|
| 方式二(自定義) | void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
- 默認(rèn): 兩個參數(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()并非只是普通的快速排序，除了對普通的快速排序進(jìn)行優(yōu)化，它還結(jié)合了插入排序和堆排序。根據(jù)不同的數(shù)量級別以及不同情況，能自動選用合適的排序方法。當(dāng)數(shù)據(jù)量較大時采用快速排序，分段遞歸。一旦分段后的數(shù)據(jù)量小于某個閥值，為避免遞歸調(diào)用帶來過大的額外負(fù)荷，便會改用插入排序。而如果遞歸層次過深，有出現(xiàn)最壞情況的傾向，還會改用堆排序。
? 所以無論元素初始時為何種狀態(tài)，sort()的平均排序復(fù)雜度為均為O(N*log2(N)) ，具有不錯的的性能，在刷算法題時，可以直接使用sort()來對數(shù)據(jù)進(jìn)行排序，而不需手動編寫排序函數(shù)。
四、sort函數(shù)使用案例
1.升序排列
sort函數(shù)如果不傳入第三個參數(shù)，則默認(rèn)是升序排列。
#include<iostream>
#include<vector>
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.降序排列
實(shí)現(xiàn)方式1
實(shí)現(xiàn)降序排列，需傳入第三個參數(shù)–比較函數(shù)，greater<type>()，這里的元素為int 類型，即函數(shù)為 greater<int>(); 如果是其他基本數(shù)據(jù)類型如float、double、long等也是同理。
#include<iostream>
#include<vector>
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;
}實(shí)現(xiàn)方式2
我們也可以使用自定義的比較函數(shù)，函數(shù)的返回值為bool類型， 例如
bool cmp(int num1, int num2) {
return num1 > num2; // 可以簡單理解為 > 降序排列; < 升序排列
}#include<iostream>
#include<vector>
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ù))
? 要對元素進(jìn)行排序，前提是元素之間可以進(jìn)行比較，即誰大誰小。 基本數(shù)據(jù)類型可直接進(jìn)行大小比較， 但結(jié)構(gòu)體元素之間的大小關(guān)系需要我們自己指定，如果不指定，則結(jié)構(gòu)體之間大小關(guān)系就不確定，則不能夠排序。
結(jié)構(gòu)體排序案例1: 對學(xué)生信息進(jìn)行排序
學(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é)生成績進(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>
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時返回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需進(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
六、補(bǔ)充：匿名函數(shù)寫法
有時自定義的排序函數(shù)比較簡單，可以使用匿名函數(shù)的形式，這樣會使代碼更加簡潔。
1.語法
在 C++ 中，匿名函數(shù)通常被稱為 “lambda 表達(dá)式”?；镜?lambda 表達(dá)式語法如下：
[capture](parameters) -> return_type { function_body }- capture：捕獲列表，定義了哪些外部變量能在 lambda 表達(dá)式中使用，以及是通過值還是引用使用它們。
- parameters：參數(shù)列表，類似于普通函數(shù)的參數(shù)列表。
- return_type：返回類型，如果函數(shù)體只包含一個
return語句，編譯器可以自動推導(dǎo)返回類型，此時可以省略。 - function_body：函數(shù)體，包含了 lambda 表達(dá)式需要執(zhí)行的代碼。
一些細(xì)節(jié):
- 當(dāng)
parameters為空的時候，()可以被省去，當(dāng)body只有return或返回為void，那么”->return-type“可以被省去。 capture：
[] // 未定義變量.試圖在Lambda內(nèi)使用任何外部變量都是錯誤的. [x, &y] // x 按值捕獲, y 按引用捕獲. [&] // 用到的任何外部變量都隱式按引用捕獲 [=] // 用到的任何外部變量都隱式按值捕獲 [&, x] // x顯式地按值捕獲. 其它變量按引用捕獲 [=, &z] // z按引用捕獲. 其它變量按值捕獲
案例1，簡單的 lambda 表達(dá)式
auto sum = [](int a, int b) { return a + b; };
cout << sum(1, 2); // 輸出：3例中，lambda 表達(dá)式定義了一個接受兩個
int參數(shù)的函數(shù)，并返回它們的和。這個 lambda 表達(dá)式被賦值給了sum變量，然后我們調(diào)用sum(1, 2)來計(jì)算1 + 2的結(jié)果。
案例2，展示了如何在 lambda 表達(dá)式中捕獲外部變量：
int factor = 2;
auto multiply = [factor](int a) { return a * factor; };
cout << multiply(3); // 輸出：6例中，lambda 表達(dá)式捕獲了外部變量
factor，并在函數(shù)體中使用它。請注意，因?yàn)?factor是通過值捕獲的，所以如果后面修改了factor的值，不會影響multiply的行為。
2. sort函數(shù)使用匿名函數(shù)
案例1
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> v(5);
for (int i = 0; i < 5; i++) v[i] = i; // 使用匿名函數(shù), 減少代碼量
sort(v.begin(), v.end(), [](int a, int b) {
return a > b; // 降序排列
});
for (int num : v) cout << num << endl;
return 0;
}案例2, 對上面學(xué)生排序使用匿名函數(shù)
#include<iostream>
#include<vector>
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ù)
};
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(), [](Student s1, Student s2) {
if (s1.grade != s2.grade) { // 如果學(xué)生成績不同
return s1.grade > s2.grade; // 則按照成績降序排列
}
return s1.name < s2.name; // 否則按照姓名升序排列
});
for (int i = 0; i < studs.size(); i++) { // 輸出結(jié)果
cout << studs[i].name << "\t" << studs[i].grade << endl;
}
return 0;
}七、參考文章鏈接
https://www.cplusplus.com/reference/algorithm/sort/
https://blog.csdn.net/qq_41575507/article/details/105936466
胡凡算法筆記
到此這篇關(guān)于C++ Sort函數(shù)詳解的文章就介紹到這了,更多相關(guān)C++ Sort函數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
今天小編就為大家分享一篇opencv3/C++ 離散余弦變換DCT方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
這篇文章主要介紹了C語言關(guān)鍵字union的定義和使用詳解,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-02-02
這篇文章主要介紹了VC小技巧匯總之控件技巧,對于VC的開發(fā)很有借鑒價值,需要的朋友可以參考下2014-07-07
C++數(shù)據(jù)結(jié)構(gòu)與算法的基礎(chǔ)知識和經(jīng)典算法匯總
終是到了標(biāo)志著大二結(jié)束的期末考試了，對于《算法設(shè)計(jì)與分析》這門課，我需要總結(jié)一下學(xué)過的所有算法的思想以及老師補(bǔ)充的關(guān)于兩個復(fù)雜度和遞歸的概念思想，以及更深層次的理解，比如用畫圖的方式表達(dá)出來，我覺得可以用博客記錄總結(jié)一下，分享給大家，希望能有所幫助2022-05-05
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)數(shù)字游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-01-01
在矩陣中考察回溯算法，分為任意起點(diǎn)、左上角開始等情況。從而有不同的模板，其實(shí)區(qū)別就是直接開始還是每個坐標(biāo)都去嘗試，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-10-10
這篇文章主要為大家詳細(xì)介紹了C語言排序算法之插入排序，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
如果不主動關(guān)閉socket的話,系統(tǒng)不會自動關(guān)閉的,除非當(dāng)前進(jìn)程掛掉了,操作系統(tǒng)把占用的socket回收了才會關(guān)閉。下面小編來簡單介紹下2019-05-05
這篇文章主要為大家詳細(xì)介紹了C語言版掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
C++實(shí)現(xiàn)重載矩陣的部分運(yùn)算符
這篇文章主要為大家詳細(xì)介紹了如何利用C++實(shí)現(xiàn)重載矩陣的部分運(yùn)算符，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)C++有一定幫助，需要的可以參考一下2022-10-10