归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
算法描述
归并操作的工作原理如下:
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
设定两个指针,最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾并成一个有序表,称为2-路归并。
#include <stdio.h> int a[13]= {6,2,3,4,1,7,9,8};
//对已经排好序的两个数组进行合并 void mergerarry(int f,int m,int l) { int i=f,j=m+1,k=f,temp[13]; while(i<=m&&j<=l) { if(a[i]<a[j]) temp[k++]=a[i++]; else temp[k++]=a[j++]; } while(i<=m) temp[k++]=a[i++]; while(j<=l) temp[k++]=a[j++]; for(k=f; k<=l; k++) a[k]=temp[k]; }
//归并 void mergersort(int f,int l) { if(f<l) { int mid=(f+l)/2; mergersort(f,mid); mergersort(mid+1,l); mergerarry(f,mid,l); } } int main() { mergersort(0,7); for(int i=0; i<8; i++) { printf("%d",a[i]); } return 0; }