首页 > 代码库 > 归并排序

归并排序

归并排序算法是遵循分治模式:

分解:分解待排序的的N个元素的序列成有N/2元素的子序列;(在不停的分解中,最终分解成一个元素,这样本生就是一个已排序的序列,此时进行合并)

解决:使用归并排序递归地排序两个子序列;

合并:合并两个已排序的子序列以产生已排序的答案

/**********************************************************
函数功能:归并排序
入口参数: int型数组,排序的左索引值,派排序的右索引   //数组的索引是数据对于数组开始的个数a[0]对应索引1。
返回值:   void   
作者  :  hx
修改日期:  2017.5.3 
**********************************************************/

#include<stdio.h>
#define   length     10
#define    max      65535
void   merge_sort(int *a,int left,int right);
void  merge(int *a,int left,int mid,int right);
int main (void)
{
  int a[length]={3,4,5,6,7,0,1,2,8,9};
  int i;
  merge_sort(a,1,10);
  for (i=0;i<10;i++)
  {
    printf("%d  ",a[i]);    
        
  }    
    printf("\n");
    return 0;
    
} 
void merge(int *a,int left,int mid,int right)
{
    int n1,n2;
    int i,j;
    n1=mid-left+1;
    n2=right-mid;
    int L[10],R[10];
    for( i=0;i<n1;i++)
    {
        L[i]=a[left+i-1];
    
    }
    for ( j=0;j<n2;j++)
    {
        R[j]=a[mid+j];
    }
    L[i]=max;
    R[j]=max;
    i=j=0;
    for(int k=left;k<right;k++)
    {
        if (L[i]<=R[j])
            a[k-1]=L[i++];
        else 
         a[k-1]=R[j++];
    }

}
void merge_sort(int *a,int left,int right)
{
    int mid;
    if(left<right){
    mid=(left+right)/2;
    merge_sort(a,left,mid);
    merge_sort(a,mid+1,right);
    merge(a,left,mid,right);
    }

}

 

归并排序