- 相關(guān)推薦
C語(yǔ)言實(shí)現(xiàn)歸并排序算法實(shí)例分析
歸并排序(Merge sort)是創(chuàng)建在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。以下是百分網(wǎng)小編搜索整理的關(guān)于C語(yǔ)言實(shí)現(xiàn)歸并排序算法實(shí)例分析，供參考學(xué)習(xí)，希望對(duì)大家有所幫助!想了解更多相關(guān)信息請(qǐng)持續(xù)關(guān)注我們應(yīng)屆畢業(yè)生考試網(wǎng)!
一個(gè)歸并排序的例子:對(duì)一個(gè)隨機(jī)點(diǎn)的鏈表進(jìn)行排序
算法描述
歸并操作的過(guò)程如下：
申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑�，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針到達(dá)序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
特點(diǎn)：歸并排序是穩(wěn)定的排序.即相等的元素的順序不會(huì)改變, 速度僅次于快速排序，但較穩(wěn)定。
歸并操作
歸并操作(merge)，也叫歸并算法，指的是將兩個(gè)順序序列合并成一個(gè)順序序列的方法。
如：設(shè)有數(shù)列 [6，202，100，301，38，8，1]
初始狀態(tài)：6, 202, 100, 301, 38, 8, 1
第一次歸并后：[6, 202], [100, 301], [8, 38], [1]，比較次數(shù)：3;
第二次歸并后：[6, 100, 202, 301]，[1, 8, 38]，比較次數(shù)：4;
第三次歸并后：[1, 6, 8, 38, 100, 202, 301]，比較次數(shù)：4;
總的比較次數(shù)為：3+4+4=11,;
逆序數(shù)為14;
算法實(shí)現(xiàn)
// Completed on 2014.10.11 17:20
// Language: C99
//
// 版權(quán)所有（C）codingwu (mail: oskernel@126.com)
// 博客地址：http://www.cnblogs.com/archimedes/
#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; //左半?yún)^(qū)域邊界
int right_min,right_max; //右半?yún)^(qū)域邊界
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;
}
使用遞歸實(shí)現(xiàn)：
// Completed on 2014.10.11 18:20
// Language: C99
//
// 版權(quán)所有（C）codingwu (mail: oskernel@126.com)
// 博客地址：http://www.cnblogs.com/archimedes/
#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;
}
【C語(yǔ)言實(shí)現(xiàn)歸并排序算法實(shí)例分析】相關(guān)文章：
C語(yǔ)言實(shí)現(xiàn)歸并排序算法實(shí)例03-19
C語(yǔ)言實(shí)現(xiàn)歸并排序算法02-04
C++歸并排序算法實(shí)例02-09
C語(yǔ)言冒泡排序算法實(shí)例06-15
C++實(shí)現(xiàn)自頂向下的歸并排序算法03-24
C++實(shí)現(xiàn)自底向上的歸并排序算法03-14