1.歸并排序
歸并排序采用的思想是分而治之，簡單來說，就是將一個待排序的序列，不斷劃分，最終得到有序的序列（只剩一個元素的序列就是有序序列），然后將這些有序的序列進行合并，第一次合并將只有一個元素序列的有序子序列進行合并，就會得到有兩個元素序列的有序子序列，然后進行第二次合并，將有兩個元素序列的有序序列進行合并，就會得到有四個元素序列的有序序列，如此下去，直到全部元素有序，
舉個例子就會一目了然：
待排序序列：1 -9 3 8 6 2 3 -1
第一次劃分：1 -9 3 8 6 2 3 -1 得到兩個序列
第二次劃分：1 -9 3 8 6 2 3 -1 得到四個序列
第三次劃分 ：1 -9 3 8 6 2 3 -1 得到8個序列，此時每個序列都是有序的，因為只有一個元素
合并
第一次合并：-9 1 3 8 2 6 -1 3 得到四個有序序列
第二次合并：-9 1 3 8 -1 2 3 6 得到兩個有序序列
第三次合并：-9 -1 1 2 3 3 6 8 得到一個有序序列，排序完成，
2.步驟
第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列 第二步：設定兩個標志，表示兩個有序序列的開始位置 第三步：比較兩個標志所指向的元素，選擇相對小的元素放入到合并空間，并移動標志到下一位置 重復步驟3直到某一個序列元素全部比較完 然后將另一序列剩下的所有元素直接復制到合并序列尾 代碼如下：（采用遞回）1 #include<stdio.h> 2 void merge(int * arr,int left,int mid,int right) 3 { 4 int i=left;//左邊子序列的起點 5 int j=mid+1;//右邊子序列的起點 6 int temp[10];//暫時陣列 7 int n=0;//本次合并元素的個數 8 9 //比較兩個序列，將符合要求的元素放進temp陣列 10 while(i<=mid&&mid<=right) 11 { 12 if(arr[i]<arr[j]) 13 temp[n++]=arr[i++]; 14 else 15 temp[n++]=arr[j++]; 16 } 17 //如果左邊序列還有剩 18 while(i<mid) 19 temp[n++]=arr[i++]; 20 21 //如果有邊序列還有剩 22 while(j<=right) 23 temp[n++]=arr[j++]; 24 25 //將排序好的元素放回原本陣列對應的位置 26 for(i=0;i<n;i++) 27 arr[left++]=temp[i]; 28 } 29 void mergeSort(int * arr,int left,int right) 30 { 31 32 if(left<right) 33 { 34 int mid=(left+right)/2;//分治 35 mergeSort(arr,left,mid);//遞回左邊序列 36 mergeSort(arr,mid+1,right);//遞回右邊序列 37 merge(arr,left,mid,right);//開始合并 38 } 39 40 } 41 int main() 42 { 43 int i; 44 int arr[10]={1,3,-9,0,10,2,8,9,19,-1}; 45 mergeSort(arr,0,9);//歸并排序 46 for(i=0;i<10;i++) 47 printf("%d\n",arr[i]); 48 return 0; 49 }
結果：
歸并排序的時間復雜度是：O(nlog?n)是一種效率很高的演算法，并且是穩定的排序演算法，穩定是指在排序的時候，相等的元素不會進行交換，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40823.html
標籤：C
下一篇：C 實戰練習題目1