sort函數(shù)
sort是c++STL標(biāo)準(zhǔn)庫中提到的基于快速排序的排序函數(shù)，在做題的時候使用sort函數(shù)很方便，使用sort要使用#include<algorithm>
快速排序具有不穩(wěn)定性
不穩(wěn)定性是指捷兰，對于指定區(qū)域內(nèi)相等的元素波附，sort函數(shù)可能無法保證數(shù)據(jù)的元素不發(fā)生相對位置不發(fā)生改變宣肚。
這對于普通的排序問題可能沒有影響溜哮，比如對于
? 2 2 3 1 5
? 排序后
1 2 2 3 1 5 （排序前第一個二可能在這里是第二個2）
但是在這里溃论，這些2么有其他含義屎蜓，對題解影響不大
！Ｔ垦炬转！但是要注意
假如上述兩個2風(fēng)別代表月份和日
那這里可能就會產(chǎn)生歧義
c++中其他有關(guān)排序的函數(shù)
sort (first, last，cmp)// 對容器或普通數(shù)組中 [first, last) 范圍內(nèi)的元素進(jìn)行排序算灸，默認(rèn)進(jìn)行升序排序扼劈。
stable_sort (first, last) // 和 sort() 函數(shù)功能相似，不同之處在于菲驴，對于 [first, last) 范圍內(nèi)值相同的元素荐吵，該函數(shù)不會改變它們的相對位置。
partial_sort (first, middle, last)// 從 [first,last) 范圍內(nèi)赊瞬，篩選出 muddle-first 個最小的元素并排序存放在 [first先煎，middle) 區(qū)間中。
partial_sort_copy (first, last, result_first, result_last)// 從
[first, last) 范圍內(nèi)篩選出 result_last-result_first 個元素排序并存儲到 [result_first,
result_last) 指定的范圍中巧涧。
is_sorted (first, last)// 檢測 [first, last) 范圍內(nèi)是否已經(jīng)排好序薯蝎，默認(rèn)檢測是否按升序排序。
is_sorted_until (first, last)// 和 is_sorted() 函數(shù)功能類似谤绳，唯一的區(qū)別在于占锯，如果 [first, last) 范圍的元素沒有排好序，則該函數(shù)會返回一個指向首個不遵循排序規(guī)則的元素的迭代器缩筛。
void nth_element (first, nth, last)// 找到 [first, last)
范圍內(nèi)按照排序規(guī)則（默認(rèn)按照升序排序）應(yīng)該位于第 nth
個位置處的元素消略，并將其放置到此位置。同時使該位置左側(cè)的所有元素都比其存放的元素小瞎抛，該位置右側(cè)的所有元素都比其存放的元素大艺演。
sort可以排序的對象：
數(shù)組（sort函數(shù)的cmp不是必須的，不寫默認(rèn)升序排序）
結(jié)構(gòu)體
什么樣的元素可以接受sort函數(shù)排序
元素類型接受使用>或<運(yùn)算符
只能對vector,array,deque這三個容器進(jìn)行排序
cmp函數(shù)的使用
sort函數(shù)在不使用 cmp函數(shù)下，默認(rèn)使用升序排序的cmp函數(shù)
升序：
```
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp1(int i,int j)
{
return i>j钞艇；//i>j返回值是bool類型,true/flase,可以用1/0來代替啄寡，假如t1表示x,y不需要互換，假如是0則需要互換.所以這里也可以這樣寫
/*if(i>j)
return 1;//前面的數(shù)大哩照，不換
else if(i<=j)//換
return 0;
*/
}
int main()
{
int a[100]={1, 51 , 65 , 1 , 8 , 9 , 8 , 52 , 89 , 21 };
sort(a,a+100,cmp1);
for(int i=0;i<100;i++)
printf("%d ",a[i]);
}
```
降序：
```
同理：
bool cmp2(int i,int j)
{
?return i<j;
/*if (i>j)
return 0;
else if(i<=j)
return 1;*/
}
```
對n個元素的a數(shù)組：sort(a,a+n,cmp)
#### 對結(jié)構(gòu)體進(jìn)行排序
對結(jié)構(gòu)體排序要構(gòu)造cmp函數(shù)
```bash
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
struct student{
int id;
int score;
}p[10];
bool cmp3(struct student i,struct student j)
{
return i.score>j.score;
}
int main()
{
for(int i=0;i<10;i++)
scanf("%d %d",&p[i].id,&p[i].score);
sort(p,p+10,cmp3);
for(int i=0;i<10;i++)
printf("id:%d score%d\n",p[i].id,p[i].score);
return 0;
}
```
結(jié)構(gòu)體數(shù)組使用sort排序和數(shù)組排序很相似
對于cmp：使用
bool (struct 結(jié)構(gòu)體 結(jié)構(gòu)體變量名,struct 結(jié)構(gòu)體 結(jié)構(gòu)體變量名）
{
return 結(jié)構(gòu)體1.待排序變量>或<結(jié)構(gòu)體2.待排序變量
}
Ｍξ铩！很多題目不會讓你只對于結(jié)構(gòu)體內(nèi)的某個變量進(jìn)行單調(diào)排序飘弧，很可能會有其他限制條件识藤，Eg:對成績排序還要考慮相同成績要排姓名首字母的問題，再比如排序生日需要排序年月日次伶。
下面用洛谷P1104題目進(jìn)行示范
cjf君想調(diào)查學(xué)校OI組每個同學(xué)的生日痴昧，并按照從大到小的順序排序。但cjf君最近作業(yè)很多冠王，沒有時間赶撰，所以請你幫她排序。
輸入：人數(shù)? ?
姓名 年 月 日
例:
3
Yangchu 1992 4 23
Qiujingya 1993 10 13
Luowen 1991 8 1
輸出：
Luowen
Yangchu
Qiujingya
分析：需要對年月日排序柱彻，先排年豪娜，年同再排月，月相同再排日：
```bash
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
struct struct{
int id;
char s[20];
int y;
int m;
int d;
}p[100];
bool cmp(mate a,mate b)
{
if(a.y<b.y)return 1;//先比年哟楷，前面小于后面就不換瘤载，因?yàn)榍懊胬?/p>
if(a.y>b.y)return 0;//前面年數(shù)大，換
if(a.y==b.y)
{
if(a.m<b.m)return 1;//再比月
if(a.m>b.m)return 0;
if(a.m==b.m)
{
if(a.d<b.d)return 1;//再比日
if(a.d>b.d)return 0;
if(a.d==b.d)
{
if(a.id>b.id)return 1;//最后比編號
else return 0;
}
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s %d %d %d",&p[i].s,&p[i].y,&p[i].m,&p[i].d);
p[i].id=i;
}
sort(p,p+n,cmp);
for(int i=0;i<n;i++)
{
if(i<n-1)
printf("%s\n",p[i].s);
else
printf("%s",p[i].s);
}
return 0;
}
```
分析：簡而言之卖擅，誰老誰在先鸣奔，就是排年，年數(shù)小就老惩阶，年同然后接著比月挎狸，月同再比日
對于上文提及的快速排序的不穩(wěn)定性，可以使用stable_sort函數(shù)琳猫，不會改變相等元素的位置
題目：洛谷P5740
>
現(xiàn)有 N(N≤1000) 名同學(xué)參加了期末考試伟叛，并且獲得了每名同學(xué)的信息：姓名（不超過 8
個字符的字符串，沒有空格）脐嫂、語文统刮、數(shù)學(xué)、英語成績（均為不超過 150
的自然數(shù)）账千〗拿桑總分最高的學(xué)生就是最厲害的，請輸出最厲害的學(xué)生各項(xiàng)信息（姓名匀奏、各科成績）鞭衩。如果有多個總分相同的學(xué)生，輸出靠前的那位。
>eg:輸入 3? ? ? ? ? ? ?
senpai 114 51 4
lxl 114 10 23
fafa 51 42 60
輸出
senpai 114 51 4
此題用結(jié)構(gòu)體很方便论衍，在獲取分?jǐn)?shù)的時候把總分存入結(jié)構(gòu)體內(nèi)瑞佩，然后對結(jié)構(gòu)體排序，輸出第一個坯台，這里最好使用stable_sort炬丸，因?yàn)榭赡艽嬖谕謹(jǐn)?shù)的情況，此時要輸入靠前的蜒蕾，這里用stable_sort很方便
遲到的代碼
```c
#include<stdio.h>
#include<algorithm>
using namespace std;
struct stu{
char a[10];
int chinese;
int math;
int english;
int score;
}p[1005];
bool cmp(struct stu x,struct stu y)
{
return x.score>y.score;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s %d %d %d",p[i].a,&p[i].chinese,&p[i].english,&p[i].math);
p[i].score=p[i].chinese+p[i].english+p[i].math;
}
stable_sort(p,p+1005,cmp);
printf("%s %d %d %d",p[0].a,p[0].chinese,p[0].english,p[0].math);
return 0;
}
```
