寫在最前：
sort(start,end,排序方法)滩租，最后一個(gè)參數(shù)可以不寫，默認(rèn)從小到大
eg:sort(a,a+10)//代表從a[0]到a[10-1]
sort(a+j+1,a+n+1)//代表從a[j]到a[n]
如果要寫第三個(gè)參數(shù)....
less<數(shù)據(jù)類型>()//從小到大排序
greater<數(shù)據(jù)類型>()//從大到小排序
eg:sort(a,a+10,less<int>());//實(shí)現(xiàn)了從小到大
sort(a,a+10,greater<int >());//實(shí)現(xiàn)了從大到小
特殊排序（適用于結(jié)構(gòu)體）
struct lizi{
int begin;
int end;
}
lizi m[maxn];
//實(shí)現(xiàn)了對(duì)m數(shù)組的以end從小到大排序
bool comp(lizi a,lizi b){
return a.end<b.end;
}
//主函數(shù)里
sort(m,m+maxn,comp);//用comp的比較方法進(jìn)行排序
參考了熊院長(zhǎng)猎莲、陳越姥姥著洼，加上自己的一些思考實(shí)現(xiàn)后COPY上來(lái)的代碼身笤，還可以繼續(xù)修改...
每個(gè)序列有許多關(guān)鍵字（主關(guān)鍵字/次關(guān)鍵字），主關(guān)鍵字可以讓一個(gè)無(wú)序序列經(jīng)排序后得到唯一的結(jié)果瞻佛；次關(guān)鍵字則不一定娇钱。
A和B的關(guān)鍵字相等文搂，排序后A、B的先后次序保持不變蔗彤，則稱這種排序算法是穩(wěn)定的疯兼。
//預(yù)備工作
#define MAXSIZE 20
typedef int KeyType;
typedef struct{
KeyType key;//關(guān)鍵字
InfoType otherinfo;//其他
}RedType;
typedef struct{
RedType r[MAXSIZE+1];//r[0]一般作哨兵或緩沖區(qū)
int length;
}SqList;
目錄：
1.冒泡排序
2.直接插入排序
3.折半查找法
4.希爾排序
5.快速排序
6.選擇排序
7.堆排序
8.歸并排序
1.冒泡排序
個(gè)人理解：
依次比較相鄰的兩個(gè)元素吧彪，如果順序不滿足我們的要求，就將其交換秧倾，直到?jīng)]有相鄰元素需要交換傀缩，達(dá)到排序成功的目的
性質(zhì)：
（1）冒泡排序是一種穩(wěn)定排序算法
（2）時(shí)間復(fù)雜度：最快O(n),平均情況O(n^2)
//自己實(shí)現(xiàn)的版本
void bubble_sort(int *a,int n){
int i,j,t;
for(i=0;i<n-2;i++){
for(j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;}}}}
//熊老師的版本赡艰，一趟下來(lái)沒有交換，可提前結(jié)束排序
void bubble_sort(SqList &L){
int m,i,j,flag=1; RedType x;
m=n-1;
while((m>0)&&(flag==1)){
flag=0;
for(j=1;j<=m;j++)
if(L.r[j].key>L.r[j+1].key){
flag=1;
x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x; //交換
}//endif
m--;
}//endwhile
}
2.直接插入排序
個(gè)人理解：
每一次將一個(gè)待排序的進(jìn)行插入揖闸，按照其關(guān)鍵字的大小插入已經(jīng)排序好的適當(dāng)位置
性質(zhì)：
（1）適用于少量數(shù)據(jù)的排序
（2）直接插入排序是一種穩(wěn)定的排序算法
（3）時(shí)間復(fù)雜度：最快O(n),平均情況O(n^2)汤纸，空間復(fù)雜度為O(1)
//將待插入的與已經(jīng)排好序的最后一位比較芹血，如果小于代表可以插入，如果大于不用排序
//將待排序的放在哨兵啃擦，然后從后往前比較哨兵和每一位的大小，如果比哨兵大的話就往后移一個(gè)慎颗，找到合適的哨兵位置言询，將其放入
void InsertSort(SqList &L){
int i,j;
for(i=2;i<=L.length;++i){//0位是哨兵运杭，1位假設(shè)已經(jīng)排好啦，從2開始
if(L.r[i].key<L.r[i-1].key){//將L.r[i]插入有序子表
L.r[0]=L.r[i];//復(fù)制為哨兵
L.r[i]=L.r[i-1];
for(j=i-2; L.r[0].key<L.r[j].key;--j)
L.r[j+1]=L.r[j];//記錄后移
L.r[j+1]=L.r[0];//插入到正確位置
}
}
}
3.折半查找法
個(gè)人理解：
直接插入排序的進(jìn)階,類似于最大子序列問題
其實(shí)就是減小了比較的次數(shù)撇眯，但沒有減少移動(dòng)次數(shù)熊榛，都是要把那個(gè)屬于待排序的位置空出來(lái)
性質(zhì)：
（1）折半查找法是一種穩(wěn)定的排序方法
（2）時(shí)間復(fù)雜度：O(n^2)腕巡，空間復(fù)雜度O(1)
void BInsertSort(SqList &L){
for(i=2;i<=L.length;++i){
L.r[0]=L.r[i];low=1;high=i-1;//將此次比較的范圍確定
while(low<=high){
m=(low+high)/2; //折半
if(L.r[0].key<L.r[m].key) high=m-1;//如果小于绘沉，說明在前半段，high變?yōu)橹虚g-1
else low=m+1; //如果大于择懂，說明在后半段另玖，low變?yōu)橹虚g+1
}
for(j=i-1;j>=high+1;--j)//此時(shí)high==low==要插入的位置
L.r[j+1] = L.r[j];//后移
L.r[high+1] = L.r[0];//插入
}
}
4.希爾排序
個(gè)人理解：
先將整個(gè)待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)赂弓，再對(duì)全體記錄進(jìn)行一次直接插入排序哪轿。
每一次通過d的大小對(duì)序列進(jìn)行“跳著”排序窃诉，然后隨著“跳”的幅度越來(lái)越小，慢慢的變成了純粹的直接插入排序飘痛，但是經(jīng)過之前的插入排序的鋪墊宣脉，工作量減小了有許多
性質(zhì)：
（1）時(shí)間復(fù)雜度是n和d的函數(shù)： O(n^1.25)~O( 1.6n^1.25)--經(jīng)驗(yàn)公式
（2）空間復(fù)雜度為 o(1)
（3）是一種不穩(wěn)定的排序方法
（4）如何選擇最佳d序列，目前尚未解決
（5）最后一個(gè)增量值必須為1竹祷，無(wú)除1以外的公因子
（6）不宜在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)
//主程序
void ShellSort(SqList &L塑陵，int dlta[],int t){//按增量序列dlta[0…t-1]對(duì)順序表L作Shell排序
for(k=0;k<t;++k)
ShellInsert(L,dlta[k]);//增量為dlta[k]的一趟插入排序
}
//單部直接插入
void ShellInsert(SqList &L,int dk){
for(i=dk+1;i<=L.length;++i){
if(r[i].key<r[i-dk].key){
r[0]=r[i];//哨兵
for(j=i-dk;j>0&&(r[0].key<r[j].key);j=j-dk)//直接插入排序
r[j+dk]=r[j];
r[j+dk]=r[0];//插入
}
}
}
5.快速排序
個(gè)人理解
分塊進(jìn)行排序
任取一個(gè)元素 (如第一個(gè)) 為中心
所有比它小的元素一律前放蜡励，比它大的元素一律后放，形成左右兩個(gè)子表兼都；
對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整俯抖，直到每個(gè)子表的元素只剩一個(gè)
性質(zhì)
（1）時(shí)間效率:O(nlog2n) --每趟確定的元素呈指數(shù)增加
（2）空間效率:O(log2n)--遞歸要用到椡咛ィ空間
（3）穩(wěn) 定 性:不穩(wěn)定--可選任一元素為支點(diǎn)
//QSort(L,1,L.length);
void QSort(SqList &L,int low,int high) {
if(low<high){
pivotloc=Partition(L,low,high);
Qsort(L,low,pivotloc-1);
Qsort(L,pivotloc+1,high);
}
}
int Partition(SqList &L,int low,int high) {
L.r[0]=L.r[low];pivotkey=L.r[low].key;
while(low<high){
while(low<high&&L.r[high].key>=pivotkey)
--high;//對(duì)于標(biāo)定位置右邊的搔啊，從右往左遍歷，找到一個(gè)比位置小的漫蛔，停止
L.r[low]=L.r[high];//把high的放到左側(cè)
while (low<high&&L.r[low].key<=pivotkey)
++low;//對(duì)于標(biāo)定位置左邊的旧蛾，從左往右遍歷，找到一個(gè)比位置大的毯盈，停止
L.r[high]=L.r[low];//把low的放到右側(cè)
}
L.r[low]=L.r[0]; //此時(shí)low==high,寫哪個(gè)無(wú)所謂病袄，把放入哨兵的值還回來(lái)即可
return low;//return high;
}
6.選擇排序
個(gè)人理解：
每次從待排序的數(shù)據(jù)元素中選出最大（小）的一個(gè)元素脑奠，存放在序列的起始位置
性質(zhì)：
（1）選擇排序是不穩(wěn)定的排序（存在爭(zhēng)議）
（2）時(shí)間復(fù)雜度：O(n2)
（3）空間復(fù)雜度：O(1)
void SelectSort(SqList &L){//對(duì)順序表L作簡(jiǎn)單選擇排序
RedType temp;
int i,j;
for(i=1;i<L.length;++i){
j=SelectMinKey(L,i);//在r[i…L.length]中選擇最小記錄并定位
if(i!=j){
temp=L.r[i];//與第i個(gè)記錄交換
L.r[i]=L.r[j];
L.r[j]=temp;
}
}
}
int SelectMinKey(SqList L,int i){
int j,min=i;
for(j=i+1;j<=L.length;j++){
if(L.r[min].key>L.r[j].key){
min=j;
}
}
return min;
}
7.堆排序
個(gè)人理解
堆：如果將序列看成一個(gè)完全二叉樹宋欺，非終端結(jié)點(diǎn)的值均小于或大于左右子結(jié)點(diǎn)的值。
利用樹的結(jié)構(gòu)特征來(lái)描述堆秒咨，所以樹只是作為堆的描述工具掌挚，堆實(shí)際是存放在線性空間中的。
那么如何用堆進(jìn)行排序陡厘？
（1）將無(wú)序序列建成一個(gè)大根堆
（2）輸出堆頂?shù)淖畲笾?br>
（3）使剩余的n-1個(gè)元素又調(diào)整成一個(gè)大根堆糙置，則可得到次大值
（4）重復(fù)執(zhí)行是目，得到一個(gè)有序序列
性質(zhì)
（1）時(shí)間效率：O(nlog2n)
（2）空間效率：O（1）
（3）堆排序是一種不穩(wěn)定的排序算法懊纳，適用于n 較大的情況
void HeapAdjust(SqList &H,int s,int m){
//已知H.r[s..m]中記錄的關(guān)鍵字除H.r[s].key之外均滿足堆的定義，本函數(shù)依據(jù)關(guān)鍵字
//的大小對(duì)H.r[s]進(jìn)行調(diào)整冤今，使H.r[s..m]成為一個(gè)大頂堆（對(duì)其中記錄的關(guān)鍵字而言）
int j;
H.r[0]= H.r[s];//暫存根結(jié)點(diǎn)的記錄
for(j=2*s;j<=m;j*=2){//沿關(guān)鍵字較大的孩子結(jié)點(diǎn)向下篩選
if(j<m&&H.r[j].key<H.r[j+1].key)
++j;//j 為關(guān)鍵字較大的孩子記錄的下標(biāo)
if(H.r[0].key>=H.r[j].key)
break;//不需要調(diào)整戏罢，跳出循環(huán)
H.r[s]=H.r[j];s=j;//將大關(guān)鍵字記錄往上調(diào)
}// for
H.r[s]=H.r[0];//回移篩選下來(lái)的記錄
}
void HeapSort( SqList &H ){//對(duì)順序表H進(jìn)行堆排序
int i;
RedType temp;
for(i=H.length/2;i>0;--i)//將 H.r[1..H.length] 建成大頂堆
HeapAdjust(H,i,H.length);
temp=H.r[1];// 互換"堆頂"和"堆底"的記錄
H.r[1]=H.r[H.length];
H.r[H.length]=temp;
for(i=H.length-1;i>1;--i) {
HeapAdjust(H,1,i);// 從根開始調(diào)整龟糕，將 H.r[1..i] 重新調(diào)整為大頂堆
temp=H.r[1];// 互換"堆頂"和當(dāng)前的"堆底"悔耘，使已有序的記錄沉積在底部
H.r[1]=H.r[i];
H.r[i]=temp;
}//for
}
8.歸并排序
個(gè)人理解
歸并：將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新有序表
排序過程
（1）初始序列看成n個(gè)有序子序列，每個(gè)子序列長(zhǎng)度為1
（2）兩兩合并催首，得到 n/2 個(gè)長(zhǎng)度為2或1的有序子序列
（3）再兩兩合并郎任，重復(fù)直至得到一個(gè)長(zhǎng)度為n的有序序列為止
性質(zhì)
（1）時(shí)間效率：O(nlog2n)
（2）空間效率：O(n)
（3）歸并排序是一種穩(wěn)定的排序方法
void Merge(RecordType SR[],RecordType TR[],int i,int m,int n){
// 將有序的SR[i…m]和SR[m+1…n]歸并為有序的TR[i…n]
int k,j;
for(k=i,j=m+1;i<=m&&j<=n;++k){
if(SR[i].key<=SR[j].key)
TR[k]=SR[i++];
else
TR[k]=SR[j++]; // 將兩個(gè)SR記錄由小到大并入TR
}
while(i<=m) {
TR[k++]=SR[i++]; // 將剩余的SR[i…m]復(fù)制到TR
}
while(j<=n){
TR[k++]=SR[j++]; // 將剩余的SR[j…n]復(fù)制到TR
}
}
void MSort(RecordType SR[],RecordTypeTR1[],int s,int t){//將無(wú)序的SR[s…t]歸并排序?yàn)門R1[s…t]
int m;
RedType TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];//當(dāng)len=1時(shí)返回
else{
m=(s+t)/2;// 將SR [s…t]平分為SR [s…m]和SR [m+1…t]
MSort(SR,TR2,s,m);// 將SR 一分為二, 2分為4…
//遞歸地將SR [s…m]歸并為有序的TR2[s…m]
MSort(SR,TR2,m+1,t);
//遞歸地將SR [m+1…t]歸并為有序的TR2[m+1…t]
Merge(TR2,TR1,s,m,t);
//將TR2 [s…m]和TR2 [m+1…t]歸并到TR1 [s…t]
}
}
void MergeSoft(SqList &L){//對(duì)順序表L作歸并排序
MSort(L.r,L.r,1,L.length);
}
