STL(第一彈)——sort函式

今天我們來講一講STL之中的sort（快排）函式

其時間復雜度為 O ( n l o g n ) O(nlogn) O(nlogn)

為何會有log的存在呢，是因為它用了二分的方法和亂數（重中之重，沒有亂數會退化成 O ( n 2 ) O(n^2) O(n2)）

sort函式分為兩種：

1. sort(_RAIter, _RAIter)
2. sort(_RAIter, _RAIter, _Compare)

翻譯后即為sort(陣列名+開始排序的數的下標（包含）,陣列名+（停止排序的數的下標+1）)

通常地，sort總是為整數陣列進行升序排序
代碼如下：

#include<cstdio>
#include<algorithm>
using namespace std;
int x[1010],n;
int main()
{
	scanf("%d",&n);//輸入需要排序的數的個數
	for(int i=1;i<=n;i++)
		scanf("%d",&x[i]);//輸入
	sort(x+1,x+1+n);//升序排序
	for(int i=1;i<=n;i++)
		printf("%d ",x[i]);//輸出
} 

程式運行結果如下
那如何才能進行降序排列呢，就要用到一個比較函式了，（個人喜歡把比較函式定義為cmp(compare的縮寫)）

代碼如下：

#include<cstdio>
#include<algorithm>
using namespace std;
int x[1000],n;
bool cmp(int a,int b)
{
	return a>b;//若此處為return a<b的話則是升序排序
}
int main()
{
	scanf("%d",&n);//輸入需要排序的數的個數
	for(int i=1;i<=n;i++)
		scanf("%d",&x[i]);//輸入
	sort(x+1,x+1+n,cmp);//降序排序
	for(int i=1;i<=n;i++)
		printf("%d ",x[i]);//輸出
} 

sort判斷換不換兩個陣列中的數時有一點特殊：

若cmp函式回傳true則不換，回傳false則換（這里可能有點不好想）

個人分辨方法便是任意一個 a = x i , b = x j ( i < j ) a=x_i,b=x_j(i<j) a=xi?,b=xj?(i<j)都會在排完序后的x陣列中符合上面的關系式a>b
運行結果如下：

還有一些結構體也可以排序，大家學過結構體的可細想一下+具體操作一下，其名稱為關鍵字排序 （ 我 們 老 師 這 樣 叫 的 ， 不 專 業 的 話 勿 噴 ） _{（我們老師這樣叫的，不專業的話勿噴）} （我們老師這樣叫的，不專業的話勿噴）?

此處有一道經典題，大家可以結合看一下

題目：
為了讓老師能更好地排出期中考試的分數，請你幫幫老師用一個程式快速排出第一到最后一名的名字

1. 總成績高的排在前面
2. 若總成績相同，語文成績高的排在前面
3. 若語文成績相同，數學成績高的排在前面
4. 若數學成績相同，英語成績高的排在前面
5. 若英語成績相同，學號靠前的排在前面（老師輸入學生成績時，總會按學號從低到高輸入）

代碼如下：

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
struct cj{
	int yuwen,shuxue,yingyu,total;
	int xuehao;
	char name[100];
}x[1010];
bool cmp(cj a,cj b)
{
	if(a.total!=b.total)return a.total>b.total;//第一關鍵字
	if(a.yuwen!=b.yuwen)return a.yuwen>b.yuwen;//第二關鍵字
	if(a.shuxue!=b.shuxue)return a.shuxue>b.shuxue;//第三關鍵字
	if(a.yingyu!=b.yingyu)return a.yingyu>b.yingyu;//第四關鍵字
	return a.xuehao<b.xuehao;//第五關鍵字
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s%d%d%d",x[i].name,&x[i].yuwen,&x[i].shuxue,&x[i].yingyu);
		x[i].xuehao=i;
		x[i].total=x[i].yuwen+x[i].shuxue+x[i].yingyu;
	}
	sort(x+1,x+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		printf("%s\n",x[i].name);
	}
} 

運行結果如下：

此處便是所有的sort的基本用法，咱們下期見！！！
下一期：STL(第二彈)——二分查找（binary_search、upper_bound、lower_bound）