C语言 实现归并排序算法
更新时间:2020年4月25日 17:33 点击:1811
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: 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, 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: 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("\n"); return 0; }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
上一篇: C++ socket实现miniFTP
下一篇: C++中Boost库裁剪与其应用详解
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04