C語言實現歸併排序算法實例
歸併排序(Merge sort)是創建在歸併操作上的一種有效的排序算法。該算法是採用分治法(Divide and Conquer)的一個非常典型的應用。
一個歸併排序的例子:對一個隨機點的鏈表進行排序
算法描述
歸併操作的過程如下:
申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合併後的序列 設定兩個指針,最初位置分別為兩個已經排序序列的起始位置 比較兩個指針所指向的元素,選擇相對小的.元素放入到合併空間,並移動指針到下一位置 重複步驟3直到某一指針到達序列尾 將另一序列剩下的所有元素直接複製到合併序列尾
特點:
歸併排序是穩定的排序.即相等的元素的順序不會改變, 速度僅次於快速排序,但較穩定。
歸併操作
歸併操作(merge),也叫歸併算法,指的是將兩個順序序列合併成一個順序序列的方法。
如:設有數列 [6,202,100,301,38,8,1]
初始狀態:6, 202, 100, 301, 38, 8, 1
第一次歸併後:[6, 202], [100, 301], [8, 38], [1],比較次數:3;
第二次歸併後:[6, 100, 202, 301],[1, 8, 38],比較次數:4;
第三次歸併後:[1, 6, 8, 38, 100, 202, 301],比較次數:4;
總的比較次數為:3+4+4=11,;
逆序數為14;
算法實現
// Completed on 2014.10.11 17:20// Language: C99//// 版權所有(C)codingwu (mail: ) // merge_sort(int *list, const int first, const int last){ int len= last-first+1; int left_min,left_max; //左半區域邊界 int right_min,right_max; //右半區域邊界 int index; int i; int *tmp; tmp = (int *)malloc(sizeof(int)*len); if( tmp == NULL || len <= 0 ) return; for( i = 1; i < len; i *= 2 ) { for( left_min = 0; left_min < len - i; left_min = right_max) { int j; right_min = left_max = left_min + i; right_max = left_max + i; j = left_min; if ( right_max > len ) right_max = len; index = 0; while( left_min < left_max && right_min < right_max ) { tmp[index++] = (list[left_min] > list[right_min] ? list[right_min++] : list[left_min++]); } while( left_min < left_max ) { list[--right_min] = list[--left_max]; } while( index > 0 ) { list[--right_min] = tmp[--index]; } } } free(tmp);}int main(){ int a[] = {288, 52, 123, 30, 212, 23, 10, 233}; int n, mid; n = sizeof(a) / sizeof(a[0]); mid = n / 2; merge_sort(a, 0, n - 1); for(int k = 0; k < n; k++) printf("%d ", a[k]); printf("n"); return 0;}
使用遞歸實現:
// Completed on 2014.10.11 18:20// Language: C99//// 版權所有(C)codingwu (mail: ) // merge(int *array,const int first, const int mid, const int last){ int i,index; int first1,last1; int first2,last2; int *tmp; tmp = (int *)malloc((last-first+1)*sizeof(int)); if( tmp == NULL ) return; first1 = first; last1 = mid; first2 = mid+1; last2 = last; index = 0; while( (first1 <= last1) && (first2 <= last2) ) { if( array[first1] < array[first2] ) { tmp[index++] = array[first1]; first1++; } else{ tmp[index++] = array[first2]; first2++; } } while( first1 <= last1 ) { tmp[index++] = array[first1++]; } while( first2 <= last2 ) { tmp[index++] = array[first2++]; } for( i=0; i<(last-first+1); i++) { array[first+i] = tmp[i]; } free(tmp);}void merge_sort(int *array, const int first, const int last){ int mid = 0; if(first < last) { mid = (first + last) / 2; merge_sort(array, first, mid); merge_sort(array, mid + 1, last); merge(array, first, mid, last); }}int main(){ int a[] = {288, 52, 123, 30, 212, 23, 10, 233}; int n, mid; n = sizeof(a) / sizeof(a[0]); mid = n / 2; merge_sort(a, 0, n - 1); for(int k = 0; k < n; k++) printf("%d ", a[k]); printf("n"); return 0;}
-
2017年3月計算機二級C語言考試摸底測試題
以下是yjbys考試網小編整理的2017年3月計算機二級C語言考試摸底測試題,希望對大家有所幫助,祝大家計算機二級考試順利通過。一、選擇題(每小題1分。)(1)程序流程圖中帶有箭頭的線段表示的是()。A.圖元關係B.數據流C.控制流D.調用關係(2)結構化程序設計的基本原則...
-
C語言if else語句彙總
對於很多情況,順序結構的代碼是遠遠不夠的,大家都接觸過C語言吧,下面是小編為大家整理的C語言ifelse語句,希望對大家有所幫助。C語言ifelse語句在C語言中,使用if和else關鍵字對條件進行判斷。請先看下面的代碼:#includeintmain(){intage;printf("請輸入你的年齡:");sc...
-
C語言精選面試題詳解
C語言是IT編程中最基礎的語言,在面試中,基本可以忽略又或者格外重要。下面是小編為大家整理的C語言精選面試題詳解,歡迎參考~分析這些面試題,本身包含很強的趣味性;而作為一名研發人員,通過對這些面試題的深入剖析則可進一步增強自身的內功。試題1:以下是引用片段:voi...
-
2017年計算機二級考試C語言備考題及答案
計算機二級對於很多考生來説還是比較有難度的,那麼怎樣順利通過二級考試呢?這就需要大家平時多練習和找方法了。以下是本站小編整理的2017年計算機二級考試C語言備考題及答案,希望對大家有幫助!1.(A)是構成C語言程序的基本單位。A、函數B、過程C、子程序D、子例...