C語(yǔ)言實(shí)現歸并排序算法實(shí)例

　　歸并排序（Merge sort）是創(chuàng )建在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應用。

　　一個(gè)歸并排序的例子:對一個(gè)隨機點(diǎn)的鏈表進(jìn)行排序

　　算法描述

　　歸并操作的過(guò)程如下：

　　申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列 設定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置 比較兩個(gè)指針所指向的元素，選擇相對小的元素放入到合并空間，并移動(dòng)指針到下一位置 重復步驟3直到某一指針到達序列尾 將另一序列剩下的所有元素直接復制到合并序列尾

　　特點(diǎn)：

　　   歸并排序是穩定的排序.即相等的元素的順序不會(huì )改變, 速度僅次于快速排序，但較穩定。

　　歸并操作

　　歸并操作(merge)，也叫歸并算法，指的是將兩個(gè)順序序列合并成一個(gè)順序序列的方法。

　　如：設有數列 [6，202，100，301，38，8，1]

　　初始狀態(tài)：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；

　　算法實(shí)現

　　// Completed on 2014.10.11 17:20// Language: C99//// 版權所有（C）codingwu (mail: oskernel@126.com) // 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;}

　　使用遞歸實(shí)現：

　　// Completed on 2014.10.11 18:20// Language: C99//// 版權所有（C）codingwu (mail: oskernel@126.com) // 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;}

【C語(yǔ)言實(shí)現歸并排序算法實(shí)例】相關(guān)文章：

C語(yǔ)言實(shí)現歸并排序算法實(shí)例分析06-28

C語(yǔ)言實(shí)現歸并排序算法08-19

C++歸并排序算法實(shí)例09-07

C語(yǔ)言冒泡排序算法實(shí)例06-15

C++實(shí)現自底向上的歸并排序算法09-09

C++實(shí)現自頂向下的歸并排序算法09-14

C語(yǔ)言中實(shí)現KMP算法實(shí)例08-09

C語(yǔ)言奇偶排序算法詳解及實(shí)例代碼10-30

C語(yǔ)言選擇排序算法及實(shí)例代碼07-25