C语言算法之归并排序代码
一、算法实现
归并排序的时间复杂度为O（nlgn），其代码实现如下：
int merge_sort(int *array, int min, int max)
{
int mid = (min+max)/2;
if(max <= min) return 0;
merge_sort(array, min, mid);
merge_sort(array, mid+1, max);
merge(array, min, mid, max);
return 0;
}
int merge(int *array, int min, int mid, int max)  
{  
    int i=0, j=0, idx=0;  
    int lnum = mid-min+1, rnum = max-mid;  
    char *L=NULL, *R=NULL;  
  
    L = calloc(1, lnum*sizeof(int));  
    if(NULL == L)  
    {  
        return -1;  
    }  
  
    R = calloc(1, rnum*sizeof(int));  
    if(NULL == R)  
    {  
        return -1;  
    }  
  
    /* Set L and R array */  
    for(i=0; i    {  
        L[i] = array[min+i];  
    }  
  
    for(j=0; j
        R[j] = array[mid+1+j];  
    }  
  
    /* Sort */  
    i =  
    j =  
    idx =  
    while(i    {  
        if(L[i]         {  
            array[idx++] = L[i++];  
        }  
        else  
        {  
            array[idx++] = R[j++];  
        }  
    }  
  
    if(i     {  
        for(; i        {  
            array[idx++] = L[i];  
        }  
    }  
    else  
    {  
        for(; j
            array[idx++] = R[j];  
        }  
    }  
  
    free(L), L=NULL;  
    free(R), R=NULL;  
    return  
}  
{–二、函数调用
#define ARRAY_NUM (10)
int main(int argc, void *argv[])
{
int idx=0;
int array[ARRAY_NUM] = {0, 9, 8, 7, 6, 5, 4, 3, 2, 1};
merge_sort(array, 0, ARRAY_NUM-1);
for(idx=0; idx<ARRAY_NUM; idx++)
{
fprintf(stdout, "array[%d] = %d\n", idx, array[idx]);
}
return 0;
}
