//首先是递归实现的方式
#include<stdio.h> #define MAXSIZE 10 //实现归并,并把数据都放在list1里面 void merging(int *list1,int list1_size,int *list2,int list2_size) { int i,j,k,m; i = j = k = 0; int temp[MAXSIZE]; while(i<list1_size&&j<list2_size) { if(list1[i] < list2[j]) { temp[k++] = list1[i++]; } else { temp[k++] = list2[j++]; } } //如果有剩下的,那么说明就是它是比前面的数组都大的,直接加入就可以了 while(i<list1_size) { temp[k++] = list1[i++]; } while(j<list2_size) { temp[k++] = list2[j++]; } for(m=0; m<(list1_size + list2_size);m++) { list1[m] = temp[m]; } } void MergeSort(int k[],int n) { if(n>1) { int *list1 = k; //定义一个指针变量,指向数组k的地址 int list1_size = n/2; //数组的长度分为本来数组长度的一半 int *list2 = k +n/2; //定义另外一个指针变量,指向数组k+n/2的地址 int list2_size = n - list1_size;//长度为刚才总的减去刚才分去那一半 MergeSort(list1,list1_size); //调用数组本身,相当与递归, MergeSort(list2,list2_size); //调用数组本身,相当与递归 merging(list1,list1_size,list2,list2_size); } } int main(){ int i,a[10] = {5,2,6,0,3,9,1,7,4.8}; MergeSort(a,10); printf("排序后的结果是:"); for(i=1; i<10; i++) { printf("%d",a[i]); } printf("\n\n"); return 0; } //归并排序复杂度分析:一趟归并需要将待排序列中的所有记录 //扫描一遍,因此耗费时间为O(n),而由完全二叉树的深度可知, //整个归并排序需要惊醒[log2n],因此,总的时间复杂度为 //O(nlogn),而且这是归并排序算法中最好、最坏平均的时间性能 //空间复杂度:由于归并过程中需要与原始记录序列同样数量级的 //存储空间去存放归并结果及递归深度为log2N的栈空间,因此空间 //复杂度为O(n+logN) //也就是说,归并排序是一种比较占内存,但却效率高且稳定的算法
没有最好只有更好,下面介绍一种用迭代方式实现归并排序的算法:
非递归的方法,避免了递归时深度为log2N的栈空间,空间只是用到归并临时申请的跟原来数组一样大小的空间,并且在时间性能上也有一定的提升,因此,使用归并排序是,尽量考虑用非递归的方法。
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 10 void MergeSort(int k[],int n) { int i,next,left_min,left_max,right_min,right_max; //开辟一个与原来数组一样大小的空间用来存储用 int *temp = (int *)malloc(n * sizeof(int)); //逐级上升,第一次比较2个,第二次比较4个,第三次比较8个。。。 for(i=1; i<n; i*=2) { //每次都从0开始,数组的头元素开始 for(left_min=0; left_min<n-i; left_min = right_max) { right_min = left_max = left_min + i; right_max = left_max + i; //右边的下标最大值只能为n if(right_max>n) { right_max = n; } //next是用来标志temp数组下标的,由于每次数据都有返回到K, //故每次开始得重新置零 next = 0; //如果左边的数据还没达到分割线且右边的数组没到达分割线,开始循环 while(left_min<left_max&&right_min<right_max) { if(k[left_min] < k[right_min]) { temp[next++] = k[left_min++]; } else { temp[next++] = k[right_min++]; } } //上面循环结束的条件有两个,如果是左边的游标尚未到达,那么需要把 //数组接回去,可能会有疑问,那如果右边的没到达呢,其实模拟一下就可以 //知道,如果右边没到达,那么说明右边的数据比较大,这时也就不用移动位置了 while(left_min < left_max) { //如果left_min小于left_max,说明现在左边的数据比较大 //直接把它们接到数组的min之前就行 k[--right_min] = k[--left_max]; } while(next>0) { //把排好序的那部分数组返回该k k[--right_min] = temp[--next]; } } } } int main(){ int i,a[10] = {5,2,6,0,3,9,1,7,4,8}; MergeSort(a,10); printf("排序后的结果是:"); for(i=0; i<10; i++) { printf("%d",a[i]); } printf("\n\n"); return 0; }
原文:http://blog.csdn.net/chencangui/article/details/44680113