C语言 实现归并排序算法
发布时间：2020-12-16 05:16:46 所属栏目：百科 来源：网络整理
导读：C语言 实现归并排序算法 归并排序（Merge sort）是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 一个归并排序的例子:对一个随机点的链表进行排序 算法描述 归并操作的过程如下： 申请空间，使其
|
C语言 实现归并排序算法 归并排序（Merge sort）是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
一个归并排序的例子:对一个随机点的链表进行排序 算法描述 归并操作的过程如下：
特点：归并排序是稳定的排序.即相等的元素的顺序不会改变, 速度仅次于快速排序，但较稳定。 归并操作 归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。 如：设有数列 [6，202，100，301，38，8，1] 初始状态：6,202,100,301,38,8,1 第一次归并后：[6,202],[100,301],[8,38],[1]，比较次数：3； 第二次归并后：[6,301]，[1,38]，比较次数：4； 第三次归并后：[1,6,301]，比较次数：4； 总的比较次数为：3+4+4=11,； 逆序数为14； 算法实现
// Completed on 2014.10.11 17:20
// Language: C99
//
// 版权所有（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; //左半区域边界
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,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: oskernel@126.com)
// 博客地址：http://www.cnblogs.com/archimedes/
#include<stdio.h>
#include<stdlib.h>
void merge(int *array,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 last)
{
int mid = 0;
if(first < last)
{
mid = (first + last) / 2;
merge_sort(array,first,mid);
merge_sort(array,mid + 1,last);
merge(array,mid,last);
}
}
int main()
{
int a[] = {288,a[k]);
printf("n");
return 0;
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
