C語言實現歸併排序算法實例分析

歸併排序(Merge sort)是創建在歸併操作上的一種有效的排序算法。該算法是採用分治法(Divide and Conquer)的.一個非常典型的應用。以下是本站小編搜索整理的關於C語言實現歸併排序算法實例分析，供參考學習，希望對大家有所幫助!想了解更多相關信息請持續關注我們應屆畢業生考試網!

一個歸併排序的例子:對一個隨機點的鏈表進行排序

　　算法描述

歸併操作的過程如下：

申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列

設定兩個指針，最初位置分別為兩個已經排序序列的起始位置

比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置

重複步驟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: )

// 博客地址：

#include<stdio.h>

#include<stdlib.h>void 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("");

return 0;

}

　　使用遞歸實現：

// Completed on 2014.10.11 18:20

// Language: C99

//

// 版權所有（C）codingwu (mail: )

// 博客地址：

#include<stdio.h>

#include<stdlib.h>

void 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("");

return 0;

}