首页 > 代码库 > 归并排序
归并排序
归并排序是分治法的典型应用。在使用分治法时，其遵循的思想是：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
分治模式在每层递归时都有三个步骤：
分解原问题为若干个子问题，这些子问题是原问题的规模较小的实例。
解决这些子问题，递归地求解各个子问题。然而，若子问题的规模足够小，则直接求解。
合并这些子问题的解成原问题的解。
下面给出一个利用分治法进行排序的实例。
#include<stdio.h>#define MAX 100000 //哨兵元素，判断子数组是否已结束void merge_array(int a[],int p,int q,int r){ int n1=q-p+1;//两个子数组的元素个数 int n2=r-q; //定义两个子数组，其中0号元素不使用，最后再添加一个哨兵元素，判断是否结束 int L[n1+2]; int R[n2+2]; //将两个字数组分别放到L[]和R[]中 for(int i=1;i<=n1;i++){ L[i]=a[p+i-1]; } for(int j=1;j<=n2;j++){ R[j]=a[q+j]; } L[n1+1]=MAX; R[n2+1]=MAX; //进行合并工作 int i=1,j=1; for(int k=p;k<=r;k++){ if(L[i]<R[j]){ a[k]=L[i]; i++; }else{ a[k]=R[j]; j++; } }}void merge_sort(int a[],int p,int r){ if(p<r){ int q=(p+r)/2; //利用递归，对两段子数组分别求序，再合并 merge_sort(a,p,q); merge_sort(a,q+1,r); merge_array(a,p,q,r); }}int main(){ int a[10]; printf("please input ten numbers:"); for(int i=0;i<10;i++){ scanf("%d",&a[i]); } merge_sort(a,0,9); printf("\nthe sorted numbers are:"); for(int j=0;j<10;j++){ printf("%d ",a[j]); } return 0;}
归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。