---

前言

算法是道路生涯的一個(gè)巨大阻礙。今日前來(lái)解決這其中之一：有關(guān)的排序算法，進(jìn)行實(shí)現(xiàn)以及性能分析。

---

一、直接插入排序算法

插入排序算法實(shí)現(xiàn)主要思想是將數(shù)據(jù)按照一定的順序一個(gè)一個(gè)的插入到有序的表中，最終得到的序列就是已經(jīng)排序好的數(shù)據(jù)。采用的方法是：在添加新的記錄時(shí)，使用順序查找的方式找到其要插入的位置，然后將新記錄插入。

直接上代碼實(shí)現(xiàn)下，學(xué)習(xí)代碼比學(xué)習(xí)概念容易的多。
代碼例子：對(duì)一個(gè)數(shù)組中的元素最終按照從小到大的順序排列輸出出來(lái)。

#include<stdio.h>
//自定義的輸出函數(shù)
void print(int a[],int n,int i)
{printf("%d:",i);for(int j=0;j<8;j++){printf("%d",a[j]);}printf("\n");
}
//直接插入排序函數(shù)
void InsertSort(int a[],int n)
{for(int i=1;i<n;i++){if(a[i]<a[i-1])//若第i個(gè)元素大于i-1元素則直接插入；反之，需要找到適當(dāng)?shù)牟迦胛恢煤笤诓迦?/span>{int j=i-1;int x=a[i];while(j>-1 && x<a[j])//采用順序查找方式找到插入的位置，在查找的同時(shí)，將數(shù)組中的元素進(jìn)行后移操作，給插入元素騰出空間。{a[j+1]=a[j];j--;}a[j+1]=x;}print(a,n,i);}
}
int main()
{int a[4]={3,1,7,5};InsertSort(a,4);
}

寫(xiě)完了代碼也差不多了解了直接插入排序算法。比如上面我們寫(xiě)的代碼實(shí)例是按照從小到大的順序排序。
實(shí)現(xiàn)的時(shí)候，遍歷所有元素，看看這個(gè)元素要插入的位置的前一個(gè)元素是否比它小，如果是的話直接插入。否則，，采用順序遍歷查找，向前遍歷尋找這個(gè)元素要插入的位置，并且將數(shù)組中的元素都進(jìn)行后移操作，給這個(gè)要插入的元素騰出空間。（元素的整體后移）
時(shí)間復(fù)雜度O（n^2）

二、折半插入排序算法

#include<stdio.h>
void print(int a[],int n,int i)
{printf("%d:",i);for(int j=0;j<n;j++){printf("%d",a[j]);}printf("\n");
}
void BInsertSort(int a[],int size)
{int i,j,low=0,high=0,mid;int temp=0;for(i=1;i<size;i++){low=0;high=i-1;temp=a[i];//采用折半查找法判斷插入的位置，最終變量low表示插入位置while(low<=high){mid=(low+high)/2;if(a[mid]>temp){high=mid-1;}else{low=mid+1;}}//有序表中插入位置后的元素統(tǒng)一后移for(j=i;j>low;j--)a[j]=a[j-1];a[low]=temp;print(a,8,i);}
}
int main()
{int a[8]={3,1,7,5,2,4,9,6};BInsertSort(a,8);
}

這其實(shí)就是把上面的直接遍歷換成了二分法尋找
折半插入排序算法相比較于直接插入排序 算法，只是減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動(dòng)次數(shù)沒(méi)有進(jìn)行優(yōu)化，所以時(shí)間復(fù)雜度仍然是O（n^2）;

三、2路插入排序算法

2-路插入排序算法的具體實(shí)現(xiàn)思路為：另外設(shè)置一個(gè)同存儲(chǔ)記錄的數(shù)組大小相同的數(shù)組d，將無(wú)序表中第一記錄添加進(jìn)d[0]的位置上，然后從無(wú)序表中第二個(gè)記錄開(kāi)始，同的d[0]做比較：如果該值比d[0]大，則添加到其右側(cè)；反之添加到其左側(cè)。

接著用上面代碼進(jìn)行改版：

#include<stdio.h>
#include<stdlib.h>
void insert(int arr[],int temp[],int n)
{int i,first,final,k;first=final=0; //分別記錄temp數(shù)組中最大值和最小值的位置temp[0]=arr[0];for(i=1;i<n;i++){//待插入元素比最小的元素小if(arr[i]<temp[first]){first=(first-1+n)%n;temp[first]=arr[i];}//待插入元素比最大元素大else if(arr[i]>temp[final]){final=(final+1+n)%n;temp[final]=arr[i];}//插入元素比最小大，比最大小else{k=(final+1+n)%n;//當(dāng)插入值比當(dāng)前值小時(shí)，需要移動(dòng)當(dāng)前值的位置while(temp[((k-1)+n)%n]>arr[i]){temp[(k+n)%n]=temp[(k-1+n)%n];k=(k-1+n)%n;}//插入該值temp[(k+n)%n]=arr[i];//因?yàn)樽畲笾档奈恢酶淖?#xff0c;所以需要實(shí)時(shí)更新final的位置final=(final+1+n)%n;}}//將排序記錄復(fù)制到原來(lái)的順序表里for(k=0;k<n;k++)arr[k]=temp[(first+k)%n];
}
int main()
{int a[8]={3,1,7,5,2,4,9,6};int temp[8];insert(a,temp,8);for(int i=0;i<8;i++)printf("%d",a[i]);return 0;
}

四、快速排序算法學(xué)習(xí)

快速排序算法實(shí)現(xiàn)的基本思想是：通過(guò)一次排序?qū)⒄麄€(gè)無(wú)序表分成相互獨(dú)立的兩部分，其中一部分中的數(shù)據(jù)都比另一部分中包含的數(shù)據(jù)的值小，然后繼續(xù)沿用此方法分別對(duì)兩部分進(jìn)行同樣的操作，直到每一個(gè)小部分不可再分，所得到的整個(gè)序列就成為了有序序列。
具體步驟如下：
（1）先從數(shù)列中取出一個(gè)元素作為基準(zhǔn)數(shù)
（2）掃描數(shù)列，將比基準(zhǔn)數(shù)小的元素全部放到它的左邊，大于或等于基準(zhǔn)數(shù)的元素全部放到它的右邊，得到左右兩個(gè)區(qū)間。
（3）再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間少于兩個(gè)元素。
接下來(lái)通過(guò)圖片展示一次這個(gè)步驟，相信剩下的應(yīng)該也就理解了。

如下實(shí)例：
（1）以數(shù)組的第一個(gè)元素作為基準(zhǔn)數(shù)，取出來(lái)，進(jìn)行另存

（2）從區(qū)間的最右邊找個(gè)比這個(gè)基準(zhǔn)數(shù)小 的數(shù)，放到 它這個(gè)位置，如下圖是找到了19.

放到原基準(zhǔn)數(shù)的位置

（3）然后再在區(qū)間的最左邊開(kāi)始找比基準(zhǔn)數(shù)大的元素找到了就放到R空的那個(gè)位置
如下圖是找到了47

放到R空的位置

（4）如此這么循環(huán)，直到L和R相遇，把這個(gè)基準(zhǔn)數(shù)填到相遇的位置

這樣基準(zhǔn)數(shù)的左邊都比基準(zhǔn)數(shù)小，基準(zhǔn)數(shù)右邊的都比基準(zhǔn)數(shù)大。
如此這么遞歸，把所有區(qū)間遞歸完，即排完序了。

接下來(lái)我們看下代碼：
代碼實(shí)例中，我特地沒(méi)在數(shù)組的第一個(gè)位置存儲(chǔ)元素，特地用它來(lái)存儲(chǔ)這個(gè)移出來(lái)，等待插入的基準(zhǔn)數(shù)

#include<stdio.h>
#include<stdlib.h>
#define MAX 9
//單個(gè)記錄的結(jié)構(gòu)
typedef struct
{int key;
}SqNote;
//記錄表的結(jié)構(gòu)體
typedef struct
{SqNote r[MAX];int length;
}SqList;
int Partition(SqList *L,int low,int high)
{L->r[0]=L->r[low]; //下標(biāo)為0的位置存放提取出來(lái)的基節(jié)點(diǎn)int pivotkey=L->r[low].key;//直到兩指針相遇，程序結(jié)束while(low<high) {//high指針左移，直到遇到比pivotkey值小的記錄，指針停止移動(dòng)while(low<high && L->r[high].key>=pivotkey){high--;	} //直接將high指向的小于支點(diǎn)的記錄移動(dòng)到low指針的位置L->r[low]=L->r[high];//low指針右移，直到遇到比pivotkey值大的記錄，指針停止移動(dòng) while(low<high && L->r[low].key<=pivotkey){low++;	} //直接將low指向的大于支點(diǎn)的記錄移動(dòng)到high指針的位置L->r[high]=L->r[low]; }//將支點(diǎn)添加到準(zhǔn)確的位置L->r[low]=L->r[0];return low; 
}
void QSort(SqList *L,int low,int high)
{if(low<high){//找到支點(diǎn)的位置int  pivotloc=Partition(L,low,high);//對(duì)支點(diǎn)左側(cè)的子表進(jìn)行排序QSort(L,low,pivotloc-1);//對(duì)支點(diǎn)右側(cè)的子表 進(jìn)行排序QSort(L,pivotloc+1,high); }
}
void QuickSort(SqList *L)
{QSort(L,1,L->length);
}
int main()
{SqList *L=(SqList*)malloc(sizeof(SqList));L->length=8;L->r[1].key=49;L->r[2].key=38;L->r[3].key=65;L->r[4].key=97;L->r[5].key=76;L->r[6].key=13;L->r[7].key=27;L->r[8].key=49;QuickSort(L);for(int i=1;i<=L->length;i++)printf("%d",L->r[i].key);return 0;
} 

快速排序算法的時(shí)間復(fù)雜度為O(nlogn)，是所有時(shí)間復(fù)雜度相同的排序方法中性能最好的排序算法。