插入排序
直接插入排序
直接插入排序（Straight Insertion Sort）的基本操作是將一個記錄插入到已經(jīng)排好序的有序表中，從而得到一個新的吹由、記錄數(shù)增1的有序表若未。
插入排序算法其實很好理解，我們在玩撲克牌的時候倾鲫，通常喜歡左手拿著排好序的牌粗合，右手拿一張牌然后在左手找位置插入萍嬉，基本上就是這個思想。我們整理牌的方法隙疚，其實就是直接插入排序壤追。
對于插入排序，我們可以有兩種構(gòu)造
- 設(shè)定哨兵位供屉，即在數(shù)組第一位留空行冰，循環(huán)中每一次要排序的那個數(shù)（從第二個數(shù)開始）先賦值給哨兵位，然后相應(yīng)數(shù)字往后移動伶丐。說到底這個哨兵位起到暫時儲存值的作用悼做。
- 用變量temp來儲存要排序的那個值，以下代碼是這個方法的實現(xiàn)哗魂。
void insertSort(int* a,int len)
{
int i,j,temp;
for(i=1;i<len;i++) //數(shù)組中從第二個數(shù)開始（假設(shè)第一個數(shù)已經(jīng)是排好的）
{ //遍歷后面每一個數(shù)肛走，進行插入排序操作
temp=a[i]; //把要排序的那個數(shù)先拿出來
for(j=i-1;a[j]>temp;j--) //逐一比較
{
a[j+1]=a[j]; //數(shù)組中在temp之前的每一個數(shù)向后移動
}
a[j+1]=temp; //找到了要插入的位置，插入
} //由于for循環(huán)中最后j--了录别，所以是a[j+1]朽色，而不是a[j]
}
希爾排序
分享一篇有助于學(xué)習(xí)希爾排序的文章：圖解希爾排序
希爾排序(Shell Sort)是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序庶灿；隨著增量逐漸減少纵搁，每組包含的關(guān)鍵詞越來越多吃衅，當(dāng)增量減至1時往踢，整個文件恰被分成一組，算法便終止徘层。
那怎么理解這個定義呢峻呕？什么是增量？
其實希爾排序的關(guān)鍵趣效，并不是隨便分組然后各自排序的瘦癌，而就是按這個增量，也就是下標(biāo)相隔的距離來進行分組跷敬，各個子序列有序讯私，跳躍排序，到最終到整體有序西傀。
選取增量的方式斤寇，是個世界難題，迄今為止沒有人找到一種最好的增量序列拥褂。
在《大話數(shù)據(jù)結(jié)構(gòu)》中是用increment = increment/3+1的方式（兼顧奇偶）娘锁，在上面分享的那篇文章，則是用gap = gap/2折半的方式來縮小增量饺鹃。
void shellSort(int* a,int n)
{ //j,i兩個循環(huán)變量莫秆，gap每次分組中元素的物理位置間隔(以元素大小為單位)间雀，x一個暫時存放插入值的變量
int j,gap=n/2,i,x;
for(gap;gap>0;gap/=2)//每次改變每組中元素的物理位置間隔
for(i=gap;i<n;i++){
//（當(dāng)不是最后一次時）當(dāng)i自加時，實質(zhì)就是跳到了下一個分組上（總是對分組的第二個元素進行排序）
x=a[i];
for(j=i-gap;j>=0&&x<a[j];j-=gap)//若x小于a[j]元素的值镊屎，
{ //則將a[j]賦值給a[j]的下一個邏輯單元并移動j到j(luò)的上一個邏輯值 （找到x的插入點的前一個邏輯點）
a[j+gap]=a[j];
}
a[j+gap]=x;//將x插入
}
}
下面我們再來看一次直接插入排序和希爾排序的動畫對比：
希爾排序不愧是第一批突破O(n^2)時間的算法惹挟，用一個簡單的思想就能夠完成高效的算法排序。
歸并排序
歸并排序（Merging Sort）是利用歸并的思想實現(xiàn)的排序方法缝驳，該算法采用經(jīng)典的==分治==（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解匪煌，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)党巾。
歸并排序的遞歸實現(xiàn)萎庭，我們需要兩個函數(shù)來完成，一個函數(shù)用于完成分而治之的工作齿拂，另一個函數(shù)調(diào)用上一個函數(shù)完成遞歸工作驳规。
代碼實現(xiàn)及其說明：
void Merge(int SR[],int TR[],int i ,int m ,int n)
{
int j,k,l;
for(j=m+1,k=i;i<=m && j<=n;k++) //兩個序列，i第一個序列起點署海，j=m+1第二個序列起點
{ //將SR中記錄有小到大歸并入TR
if (SR[i]<SR[j])
TR[k]=SR[i++]; //第一個序列的第一個比第二個序列的第一個小吗购，所以賦值然后i+,取第一個序列的下一個
else
TR[k]=SR[j++];
}
if(i<=m)
{
for (l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; //將剩余的SR[i...m]復(fù)制到TR
}
if(j<=n)
{
for (l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; //將剩余的SR[j...m]復(fù)制到TR
}
}
void MSort(int SR[],int TR1[],int s,int t )
{
int m;
int TR2[MAXSIZE+1];
if (s==t)
{
TR1[s]=SR[s];
}
else
{
m=(s+t)/2;//將SR平分為兩個SR
MSort(SR,TR2,s,m);//遞歸將SR（前半段）歸并為有序的TR2
MSort(SR,TR2,m+1,t);//遞歸將SR（后半段）歸并為有序的TR2
Merge(TR2,TR1,s,m,t); //傳三個參數(shù)目的 起點，分離點 砸狞，終點
//將TR2（前半段）和TR2（后半段）歸并到TR1
}
}
/**
*代碼來自《大話數(shù)據(jù)結(jié)構(gòu)》捻勉，我們要使用寫好的歸并排序，就是調(diào)用 MSort()函數(shù)
* 參數(shù)說明：SR[]和TR1[]最開始傳參的時候都是傳入數(shù)組a
* s和t分別是1和最大下標(biāo)刀森，數(shù)組下標(biāo)從1開始
* MSort()的作用：將SR[s...t]歸并排序為TR1[s...t]
* Merge()的作用：將有序的SR[i...m]和SR[m+1...n]歸并為有序的TR[i...n]
*/
