1）插入排序（把a(bǔ)[i]插入到a[0]...a[i-1]的合適位置）
原理：遍歷數(shù)組，遍歷到a[i]時，a0,a1...ai-1是已經(jīng)排好序的，取出ai，從ai-1開始向前和每個比較大小，如果小于，則將此位置元素向后移動，繼續(xù)先前的比較，如果不小于，在放在正在比較的元素之后?？梢娤嗟仍乇容^是原來靠后的還是排在后邊，所以插入排序是穩(wěn)定的。
當(dāng)待排序的數(shù)據(jù)基本有序時，插入排序的效率比較高，只需要進(jìn)行很少的數(shù)據(jù)移動。
1 function insertion_sort(int a[],int n){ 2 int i,j,v; 3 for(i=1;i<n;i ){ 4 //比較處理a[i] 5 for(v=a[i],j=i-1;v<a[j];j--){ 6 a[j 1]=a[j]; 7 } 8 a[j 1]=v; 9 } 10 }2）選擇排序（從a[i-1]后續(xù)元素中選擇最小的放到a[i]位置）
原理：遍歷數(shù)組，遍歷到i時，a0,a1...ai-1是已經(jīng)排好序的，然后從i到n選擇出最小的，記錄下位置，如果不是第i個，則和第i個元素交換。此時第i個元素可能會排到相等元素之后，所以選擇排序是不穩(wěn)定的。
function selection_sort(int a[],int n){ int i,j,pos,temp; for(i=0;i<n-1;i ){ //查詢最小值的下標(biāo),記錄在pos中 for(pos=i;j=i 1;j<n;j ){ if(a[pos]>a[j]){ pos=j; } } if(pos!=i){ temp = a[i]; a[i] = a[pos]; a[pos] = temp; } }} 3）冒泡排序
冒泡排序名字很形象，實(shí)際實(shí)現(xiàn)是相鄰兩個節(jié)點(diǎn)做比較，大的向后移一個，經(jīng)過第一輪兩兩比較和移動，最大的元素就移動到了最后，第二輪次大的元素移動到了倒數(shù)第二個，依次進(jìn)行。冒泡排序相等元素位置不會發(fā)生交換，是穩(wěn)定的。這是最基本的冒泡排序，可以進(jìn)行優(yōu)化。
優(yōu)化一：如果某一輪兩兩比較中沒有任何元素交換，這說明已經(jīng)都排好序了，算法結(jié)束，可以使用一個Flag做標(biāo)記，默認(rèn)為false，如果發(fā)生交換則置為true，每輪結(jié)束時檢查Flag，如果為true則繼續(xù)，如果為false則返回。
優(yōu)化二：某一輪結(jié)束位置為i，但是這一輪的最后發(fā)生交換位置為lastSwap，則lastSwap到j(luò)之間是排好序的，下一輪結(jié)束點(diǎn)就不必是j--了，而直接到lastSwap即可，代碼如下：
1 function bubble_sort(int a[],int n){ 2 int i,j,lastSwap,temp; 3 for (i=n-1;i>0;i=lastSwap){ 4 for(j=0;j<i;j ){ 5 if(a[j]>a[j 1]){ 6 temp = a[j 1]; 7 a[j 1] = a[j]; 8 a[j] = temp; 9 //最后一次交換位置的坐標(biāo)10 lastSwap = j;11 }12 }13 }14 }4）快速排序
原理：快速排序首先找到一個基準(zhǔn)存儲到pivot中，用（L）標(biāo)識數(shù)組查詢左端，用（R）標(biāo)識數(shù)組查詢右端，一般以第一個元素作為基準(zhǔn)（pivot）。 然后先從最右邊（R）向左搜索，如果發(fā)現(xiàn)比pivot小的，則把改元素放到a[L]中，L ，然后再從左（L）向右搜索，如果發(fā)現(xiàn)比pivot大的，則將其放到a[R]中（注意此時a[R]的值早就放到左端了，此時a[R]的值早就沒用了，這也是為什么右一個左一個查找的原因）。經(jīng)過一輪比較后pivot的值就正好排在了排好序后應(yīng)該在的位置，而pivot左端的都是小于等于他的值，右端的都是大于等于它的值。之后對左右兩端遞歸調(diào)用該方法，最后就完成了排序。快速排序是一種不穩(wěn)定的排序。
1 //劃分定位基準(zhǔn)值 2 int mPartition(int a[],int L,int R){ 3 int pivot = a[L]; 4 while(L<R){ 5 while(L<R && a[R]>pivot){//正常，繼續(xù)往左查找 6 R--; 7 } 8 if(L<R){//將小值放到左端 9 a[L]=a[R];10 L ;11 }12 while(L<R && a[L]<pivot){13 L ;14 }15 if(L<R){//將大值放到右端16 a[R]=a[L];17 R--;18 }19 }20 //將基準(zhǔn)值放到正確位置L,返回改位置作為下次查找定界21 a[L] = pivot;22 return L;23 }24 25 //快速查找26 void quick_sort(int a[],int L,int R){27 int q;28 if(L<R){29 q = mPartition(a,L,R);30 //遞歸調(diào)用31 quick_sort(a,L,q-1);32 quick_sort(a,q 1,R);33 }34 }5）堆排序
原理：堆排序是把數(shù)組看成堆，第i個節(jié)點(diǎn)的孩子為2*i 1和2*i 2個結(jié)點(diǎn)（不超出數(shù)組長度前提下）。第一步：將無序數(shù)組建成一個堆（升序建大頂堆，降序建小頂堆）；第二步：將堆頂元素與末尾交換，最大元素“沉”到數(shù)組末端；第三步：重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整和交換步驟，直到整個序列有序。
下述代碼使用大頂堆（從小到大排序）。堆排序的過程是自左向右，自底向上的，這樣在調(diào)整某個節(jié)點(diǎn)時，其左節(jié)點(diǎn)和右節(jié)點(diǎn)已經(jīng)是滿足條件的，兩個節(jié)點(diǎn)不需要動，整個子樹也不需要動了。堆排序的主要時間花在初始建堆期間，堆排序是一種不穩(wěn)定排序。堆排序不適宜記錄數(shù)較少的排序。
1 //建堆 2 void headAdjust(int a[],int i,int nLength){ 3 int nChild,nTemp; 4 for(nTemp = a[i];2*i 1 < nLength;i = nChild){ 5 //子節(jié)點(diǎn)位置 = 2*（父節(jié)點(diǎn)位置） 1; 6 nChild = 2 * i 1; 7 //獲取子節(jié)點(diǎn)中較大的節(jié)點(diǎn) 8 if(nChild < nLength-1 && a[nChild 1] > a[nChild]){ 9 nChild ;10 }11 //如果較大的子節(jié)點(diǎn)大于父節(jié)點(diǎn)那么把子節(jié)點(diǎn)往上移，替換父節(jié)點(diǎn)12 if(nTemp < a[nChild]){13 a[i] = a[nChild];14 a[nChild] = nTemp;15 }else{//子節(jié)點(diǎn)不需要動，則整個子樹不需要動16 break;17 }18 }19 }20 21 //堆排序22 void heap_sort(int a[],int length){23 int temp;24 //堆排序從左到右從底向上排序，所以最后一個非葉節(jié)點(diǎn)開始（length/2-1）;25 for(int i = length/2-1; i>=0;i--){26 headAdjust(a,i,length)27 }28 //交換堆頂和最后一個子元素，重新執(zhí)行建堆操作29 for(int i = length-1;i>0;i--){30 temp = a[0];31 a[0] = a[i];32 a[i] = temp;33 headAdjust(a,0,i);34 }35 }6）歸并排序
原理：歸并排序是分之策略的典型應(yīng)用。其基本思想是：首先考慮將兩個有序數(shù)列合并時，這個非常簡單，只要比較兩個數(shù)列的第一個數(shù)，然后誰小取誰，取了之后在對應(yīng)數(shù)列中刪除這個數(shù)，然后繼續(xù)比較。如果有數(shù)列為空，那將另一個數(shù)列中剩余的數(shù)取出來即可。歸并排序首先將數(shù)列采用遞歸方式分成兩兩有序數(shù)列，然后按照上述方式歸并生成新數(shù)列，然后再一步步向上回歸，最終歸并成完整有序數(shù)列。
有的地方可以看到在mergeArray中合并有序數(shù)列是分配臨時數(shù)組，即每一步在mergeArray的結(jié)果都存放在一個新的臨時數(shù)組中，每次在mergeArray中新建一個數(shù)組在遞歸中會消耗大量的空間。這里做一個小小的變化，只需要在merge_sort中新建一個數(shù)組，并傳入mergeArray中，后面的操作都會公用這個臨時數(shù)組，合并完后將臨時數(shù)組中的數(shù)據(jù)寫會原數(shù)組中。這樣僅需要與原始數(shù)據(jù)同樣數(shù)量的存儲空間存放歸并數(shù)據(jù)，因此空間復(fù)雜度為O(n)。
歸并排序中數(shù)據(jù)兩兩比較，不存在跳躍，因此歸并排序是一種穩(wěn)定排序。
1 //合并連個有序數(shù)組 2 void mergeArray(int a[],int first ,int mid,int last,int temp){ 3 int i=first,j=mid 1; 4 int m = mid,n=last; 5 int k=0; 6 while(i<=m && j<=n){ 7 if(a[i]<=a[j]){ 8 temp[k ] = a[i ]; 9 }else{10 temp[k ] = a[j ];11 }12 }13 //如果第一個數(shù)組還有剩余數(shù)據(jù)，直接取出插入14 while(i<=m){15 temp[k ] = a[i ];16 }17 //如果第二個數(shù)組還有剩余數(shù)據(jù)，直接取出插入18 while(j<=n){19 temp[k ] = a[j ];20 }21 //存回原數(shù)組22 for(i=0;i<k;i ){23 a[first i] = temp[i];24 }25 }26 27 //歸并排序28 void merge_sort(int a[],int first,int last,int temp[]){29 if(first<last){30 int mid = (first last)/2;31 merge_sort(a,first,mid,temp);//使左邊有序32 merge_sort(a,mid 1,last,temp);//使右邊有序33 mergeArray(a,first,mid,last,temp);//將左右兩邊合并34 }35 }7）希爾排序（改進(jìn)的插入排序）
原理：希爾排序是對 插入排序的優(yōu)化，其基于以下兩個認(rèn)識：1.數(shù)據(jù)量較小時插入排序速度較快，因?yàn)閚和n2差距很??；2.數(shù)據(jù)基本有序時插入排序效率很高，因?yàn)楸容^和移動的數(shù)據(jù)量小。
因此，希爾排序的基本思想是將需要排序的序列劃分成為若干個較小的序列，對子序列進(jìn)行插入排序，然后對較小的有序數(shù)列再進(jìn)行插入排序，這樣能夠提高排序算法的效率。
希爾排序劃分子序列不是像歸并排序那樣的二分，而是采用的叫做增量的技術(shù)，列如對有10個元素的數(shù)組進(jìn)行希爾排序，首先增量設(shè)為10/2=5,此時第一個元素和第（1 5）個元素配對成子序列使用插入排序進(jìn)行排序，第2和第（2 5）個元素組成子序列……，完成后增量繼續(xù)減半為2，此時第一個元素和第（1 2）、（1 4）、（1 6）、（1 8）個元素組成子序列進(jìn)行插入排序。這種增量選擇方法的好處是可以使數(shù)組整體均勻有序，盡可能的減少比較和移動的次數(shù)。而二分法中即使前一半有序，后一半中如果有較小的數(shù)據(jù)，還是會造成大量的比較和移動，因此這用增量的方法和插入排序的配合更加。
希爾排序的時間復(fù)雜度和增量的選擇策略有關(guān)，希爾排序是一種不穩(wěn)定排序。
1 void shell_sort(int a[],int length){ 2 int step,i,j,temp; 3 for(step = length/2;step>=1;step = step/2){//增量每次減半，減到1時完成排序 4 for(i = step;i<length;i ){ 5 temp = a[i];//temp為插入排序中本輪待插入的元素a【i】，此時a[i-step]...已有序 6 for(j = i-step;j>=0&&a[j]>temp;j = j-step){//a[i]尋找和自己同組的元素進(jìn)行比較 7 a[j step] = a[j];//大的元素往后移 8 } 9 a[j step] = temp;//將temp放在最終位置 10 }11 }12 }8）二叉樹排序
原理：二叉樹排序借助了數(shù)據(jù)結(jié)構(gòu)中二叉排序數(shù)，二叉排序樹滿足三個條件：（1）若左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；（2）若右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；（3）左、右子樹也分別為二叉排序樹。根據(jù)這三個特點(diǎn)，用中序遍歷二叉樹得到的結(jié)果就是排序的結(jié)果。
二叉樹排序法需要首先根據(jù)數(shù)據(jù)構(gòu)建二叉排序樹，然后中序遍歷，排序時間復(fù)雜度為O(nlogn)，構(gòu)建二叉樹需要額外的O(n)的存儲空間，二叉樹排序是穩(wěn)定的。
在實(shí)現(xiàn)此算法的過程中遇到不小的困難，指正參數(shù)在函數(shù)中無法通過new賦值，后來采取指針地址，然后函數(shù)設(shè)置BST** tree的方式解決。
1 int arr[] = {7, 8, 8, 9, 5, 16, 5, 3,56,21,34,15,42}; 2 3 struct BST{ 4 int number;//保存數(shù)組元素的值 5 struct BST * left; 6 struct BST * right; 7 8 }; 9 10 void insertBST(BST**tree,int v){11 if(*tree == NULL){12 *tree = new BST;13 (*tree)->left = (*tree)->right = NULL;14 (*tree)->number = v;15 return;16 }17 if(v<(*tree)->left){18 insertBST(&((*tree)->left), v);19 }else{20 insertBST(&((*tree)->right), v);21 }22 23 }24 25 void printResult(BST * tree){26 if(tree == NULL){27 return;28 }29 if(tree->left!=NULL){30 printResult(tree->left);31 }32 cout << tree->number << " ";33 if(tree->right !=NULL){34 printResult(tree->right);35 }36 }37 38 void createBST(BST ** tree,int a[],int n){39 *tree = NULL;40 for(int i =0;i<n;i ){41 insertBST(tree,a[i]);42 }43 }44 45 int main(){46 int n = sizeof(arr)/sizeof(int);//計(jì)算數(shù)組元素個數(shù)，因?yàn)閿?shù)組元素為int型，所以/sizeof(int)47 BST * root;48 creatBST(&root,arr,n);49 printResult(root);50 }
聯(lián)系客服
