前言
這次會介紹一些排序的方法贬蛙，有些我會只說方法，思路锰提。重點講c++自帶函數(shù)sort
這篇文章不會涉及快排曙痘，因為寫快排的博客實在太多啦。立肘。而且我覺得大多數(shù)人應(yīng)該都會边坤。
選擇排序
基本思想：每次把最大（或最小）的一個元素放在待排序數(shù)組的最前谅年，然后縮小待排序數(shù)組茧痒，直到全部排序完成
例子：
原始數(shù)組：[49 38 65 97 76]
第一次：38[49 65 97 76]
第二次：38 49[65 97 76]
第三次：38 49 65[97 76]
第四次：38 49 65 76 [97]
最后一次：38 49 65 76 97
這個的實現(xiàn)方法太暴力了，就不附上源碼融蹂，有興趣的話可以自己試著寫一下
冒泡排序
基本思想：一個數(shù)組旺订，每次抓相鄰的兩個元素來比較，如果滿足大小關(guān)系超燃，就繼續(xù)区拳，如果不滿足就交換。
步驟：
1.讀入數(shù)據(jù)存在a數(shù)組中
2.比較相鄰的前后兩個數(shù)據(jù)意乓，如果前面的數(shù)據(jù)大于（或小于）后面的數(shù)據(jù)樱调，就把兩個數(shù)據(jù)交換。
3.對數(shù)組的第0個數(shù)據(jù)到n-1個數(shù)據(jù)進行一次遍歷后，最大（或最邪柿琛）的一個數(shù)就“冒”到數(shù)組第n-1個位置圣猎。
4.n=n-1，如果n不為0就重復(fù)前面兩步菩颖，否則排序完成样漆。
源碼：
for(int i=n-1;i>=1;i--)//進行n-1輪冒泡
{
for(int j=0;j<=i;j++)//每輪進行i次比較
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);//交換相鄰兩個元素，注：swap需要using namespace std;這一句
}
}
}
插入排序
基本思想：就像打撲克牌抽牌的時候一樣晦闰，邊抽牌放祟，邊放在恰當(dāng)?shù)奈恢茫ネ昱频臅r候呻右，手上的牌就已經(jīng)排好序了跪妥。
在讀入一個元素的時候，在已經(jīng)排好的序列中声滥，搜尋他的正確位置（前面的元素比他小眉撵，后面的元素比他大）。但是在插入一個元素之前落塑，需要把元素后面的每一個元素向后挪一位纽疟。
也是暴力算法，時間效率不高憾赁，不是很推薦污朽。
有興趣的同學(xué)可以自己去寫一下試試。
桶排序
典型的犧牲空間省時間
基本思想：若要排序的元素的值在一個明顯有限范圍內(nèi)時龙考，可以設(shè)計有限個有序桶蟆肆，把待排序的值裝入對應(yīng)的桶，桶號就是待排序的值晦款，順序輸出各桶的值炎功，就得到有序排列。
源碼
for(int i=1;i<=n;i++)
{
cin>>a;
b[a]++;//裝桶
}
值得一提的是缓溅，在裝入之前蛇损，要把b數(shù)組清空。
然后只需要輸出b數(shù)組所有不為零的元素即可坛怪。
歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法州藕，這是采用分治法的一個很好的典型。
主要思路
將已有序的字序列合并酝陈，得到完全的有序序列床玻，就是先使小的子序列有序，在使子序列段間有序沉帮。還記得分治算法的基礎(chǔ)思路嗎锈死？就是把大的問題分解成小的問題贫堰，在逐步解決小的問題，從而解決大的問題待牵。
這里給出偽代碼（不是我寫的）
是遞歸實現(xiàn)其屏，所以比較好懂，代碼注釋是我加的缨该。
void merge(int a[],int n,int left,int mid,int right)
{
int n1=mid-left,n2=right-mid;//注意此處n1,n2不是指針偎行，而是表示區(qū)間長度
for(int i=0;i<n1;i++)
L[i]=a[left+i];//操作左子序列
for(int i=0;i<n2;i++)
R[i]=a[mid+i];//操作右子序列
L[n1]=R[n2]=INF;
int i=0,j=0;
for(int k=left;k<right;k++)//把子序列整合到一個序列中
{
if(L[i]<=R[j])
a[k]=L[i++];
else
a[k]=R[j++];
}
}
void mergesort(int a[],int n,int left,int right)
{
if(left+1<right)
{
int mid=(left+right)/2;//找到中間的元素，方便分解左子序列和右子序列
mergesort(a,n,left,mid);//分解左子序列
mergesort(a,n,mid,right);//分解右子序列
merge(a,n,left,mid,right);//合并左右子序列贰拿，從而得到一個已被排好序的數(shù)組
}
}
歸并排序的時間復(fù)雜度是o(nlogn)速度較快蛤袒，同時它是最穩(wěn)定的排序。
sort
其實我我最想介紹的就是這個膨更。它非常好用妙真，基本可以應(yīng)付任何排序的需要，甚至都可以對結(jié)構(gòu)體進行排序荚守。
sort需要的頭文件：
#include<algorithm>
sort的格式（用法）：假如你的數(shù)組a,是從a[0]開始儲存的珍德，并且數(shù)組長度為n，那么sort這么寫：
sort(a,a+n,comp);
假如你的數(shù)組a是從a[1]開始存儲的矗漾，那么sort這么寫：
sort(a+1,a+n+1,comp);//注意要寫+1
comp
事實上你可以給這個函數(shù)取個別的名字锈候，沒有規(guī)定它必須叫啥，總之要寫在那個位置就是了敞贡。
comp是讓sort神化的一個主要原因泵琳。
comp就像是你制定的規(guī)則，它會按照你制定的規(guī)則來嫡锌。
comp不是一定要打，如果不打comp的話他就回默認從小到大排序琳钉。
下面我會舉幾個例子來說明comp的用法势木。
一般數(shù)據(jù)類型排序
假如你想從大到小排序
inline void comp(int x,int y)//其實這個x和y你可以自己取名字，對于其他類型你只需要把int改成其他類型
{
return x>y;//其實這里很形象歌懒，你的數(shù)組的每一項都大于它的后一項
}
從小到大的comp函數(shù)你肯定也會寫了啦桌。
值得一提的是：sort也可以排序string類型，char類型及皂。
string類型的會按照字典序排序甫男。
結(jié)構(gòu)體排序
假設(shè)你有這樣一個結(jié)構(gòu)體
struct student
{
string name;
int points;
}
假如你要按照points為關(guān)鍵字，從大到小排序验烧。
bool comp(student x,student y)//注意這里要寫結(jié)構(gòu)體的數(shù)據(jù)名稱
{
return x.points>y.points;
}
是不是很簡單呢板驳？
升級一下：假如分數(shù)相同，那么把名字作為第二關(guān)鍵字碍拆，按字典序降序排
bool comp(student x,student y)
{
if(x.points==y.points)
return x.name<y.name;
return x.points>y.points;
}
其實也就是加一個特殊判斷罷了若治。
說一下慨蓝，sort的時間復(fù)雜度和快排的一樣。
ending
排序是各大競賽中很重要的一項基本功端幼，許多算法都是建立在排序基礎(chǔ)上的礼烈。有些貪心題可以直接排序，然后就輸出了婆跑。
說了那么多此熬。。你自己去用用滑进？
