//首先是递归实现的方式#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)//也就是说，归并排序是一种比较占内存，但却效率高且稳定的算法
没有最好只有更好，下面介绍一种用迭代方式实现归并排序的算法：
#include<stdio.h>#include<stdlib.h>#define MAXSIZE 10void 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;//右边的下标最大值只能为nif(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){//把排好序的那部分数组返回该kk[–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;}
，鸟的翅膀在空气里振动，那是一种喧嚣而凛裂的，
