学步园

#include<stdio.h>
#include<stdlib.h>
#define INF 0x7fffffff
//归并排序的非递归实现

//将[l,mid]和[mid+1,r]归并到一起 l<=mid<r
void merge(int a[],int l,int mid,int r){
    int i,j;
    int n1=mid-l+1;
    int n2=r-mid;
    int *left=new int[n1+1];
    for(i=0;i<n1;i++)
        left[i]=a[i+l];
    left[n1]=INF;
    int *right=new int[n2+1];
    for(i=0;i<n2;i++)
        right[i]=a[i+mid+1];
    right[n2]=INF;
    
    i=j=0;
    for(int k=l;k<=r;k++){
	    if(left[i]<right[j])
	        a[k]=left[i++];
	    else
	        a[k]=right[j++];
	}
}
//对区间[l,r]进行归并排序 
void merge_sort(int a[],int l,int r){
	int len=r-l+1;
	//枚举的是一半的长度 
       for(int i=1;i<=len;i*=2){
 	        int left=l;
	        while(left<r){
		    int mid=left+i-1;
		    int right=left+2*i-1;
		    //中间值大于右边界，说明排好序了 
		    if(mid>r) break;
		    //中间值没有超，右边界超了 
		    if(right>r) right=r;
		    //mid和right相等的时候，也不需要排序 
		    if(right==mid) break;
		    merge(a,left,mid,right);
		    left=right+1; 
		}
	}
}
int main(){
	int b[]={7,5,4,6,9,2,1,0,3,6};
	merge_sort(b,0,9);
	for(int i=0;i<10;i++)
	    printf("%d ",b[i]);
	system("pause");
    return 0;
}