首页 > 代码库 > 归并排序
归并排序
归并排序就是把数组A分成2个数组A1和A2,再对A1和A2也分别平分,直到不能分为止,即只有1个元素了.再依次合并.是一个分和合的过程.
代码是在ubuntu下的vim里写的.我加了很多打印,从打印结果里面可以看出程序是怎么一步一步执行的,本来要画个图的,因为没找到比较好的工具(ubuntu下),比较好是说可以画的漂亮,而且有剪切功能.
#include<stdio.h>#include<malloc.h>void mergesort(int source[], int ordered[], int startIndex, int endIndex);void merge(int source[], int ordered[], int startIndex, int midIndex, int endIndex);int main(){ int a[8] = {3,2,1,6,7,4,8,5}; int b[8]; int i; printf("排序前的乱序数组:"); for(i = 0; i < 8; ++i) printf("%d ",a[i]); printf("\n\n"); mergesort(a,b,0,7); printf("排序后的有序数组:"); for(i = 0; i < 8; ++i) printf("%d ",b[i]); printf("\n"); return 0;}void mergesort(int source[], int ordered[], int startIndex, int endIndex){ if(startIndex == endIndex) { ordered[startIndex] = source[startIndex]; } else { int *tmp = (int*)malloc((endIndex-startIndex+1)*sizeof(int)); int mid = (startIndex + endIndex)/2; printf("(startIndex,midIndex,endIndex) = "); printf("(%d,%d,%d)\n",startIndex,mid,endIndex); mergesort(source,tmp,startIndex,mid); mergesort(source,tmp,mid+1,endIndex); printf("需要排序的两个数组是:"); int i; for(i = startIndex; i <= endIndex; ++i) { printf("%d ",tmp[i]); if(i == mid) printf("和 "); } printf("\n"); //保证用来合并的数组有序,所以第一个参数是tmp. merge(tmp,ordered,startIndex,mid,endIndex); }}void merge(int source[], int ordered[], int startIndex, int midIndex, int endIndex){ int i = startIndex, j = midIndex + 1,k = startIndex; while(i <= midIndex && j <= endIndex) { if(source[i] < source[j]) { ordered[k++] = source[i++]; } else { ordered[k++] = source[j++]; } } while(i<=midIndex) ordered[k++] = source[i++]; while(j<=endIndex) ordered[k++] = source[j++]; printf("合并后的结果是:"); for(i = startIndex; i <= endIndex; ++i) printf("%d ",ordered[i]); printf("\n\n");}
编译结果:
排序前的乱序数组:3 2 1 6 7 4 8 5 (startIndex,midIndex,endIndex) = (0,3,7)(startIndex,midIndex,endIndex) = (0,1,3)(startIndex,midIndex,endIndex) = (0,0,1)需要排序的两个数组是:3 和 2 合并后的结果是:2 3 (startIndex,midIndex,endIndex) = (2,2,3)需要排序的两个数组是:1 和 6 合并后的结果是:1 6 需要排序的两个数组是:2 3 和 1 6 合并后的结果是:1 2 3 6 (startIndex,midIndex,endIndex) = (4,5,7)(startIndex,midIndex,endIndex) = (4,4,5)需要排序的两个数组是:7 和 4 合并后的结果是:4 7 (startIndex,midIndex,endIndex) = (6,6,7)需要排序的两个数组是:8 和 5 合并后的结果是:5 8 需要排序的两个数组是:4 7 和 5 8 合并后的结果是:4 5 7 8 需要排序的两个数组是:1 2 3 6 和 4 5 7 8 合并后的结果是:1 2 3 4 5 6 7 8 排序后的有序数组:1 2 3 4 5 6 7 8
从打印结果可以自己手动执行归并排序的过程了吧?
归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。