首页 > 代码库 > 经典排序之归并排序
经典排序之归并排序
归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
#include <stdio.h>#include <stdlib.h>/*归并排序mergeSort说明：mergeSort需要借助一个O(n)大小的空间存储排序数组，*/void merge(int *a,int first,int mid,int last,int *p){ int i = first,j=mid+1; int k = first; while(i<=mid&&j<=last) { if(a[i]<a[j])p[k] = a[i++]; else p[k]=a[j++]; k++; } while(i<=mid)p[k++] = a[i++]; while(j<=last)p[k++] = a[j++]; for (int i = first; i <= last; i++) { a[i] = p[i]; }}void mergeSort(int *a,int first,int last,int *p){ if(first < last) { int mid = (last+first)/2; mergeSort(a,first,mid,p); mergeSort(a,mid+1,last,p); merge(a,first,mid,last,p); } }int main(int argc, char **argv){ int a[] = {2,24,3,19,45,12,1,66,34,7}; int size; int i; size = sizeof(a)/sizeof(int); int *p = (int*)malloc(sizeof(int)*(size+1)); mergeSort(a,0,size-1,p); for(i = 0; i < size; i++) { printf("%d ",a[i]); } printf("\n"); free(p); return 0;}
经典排序之归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。