归并排序

思想

分而治之

1. divide: 将数组从中间分成左右两个子数组
2. conquer：使用递归对子数组进行排序
3. combine： 合并有序子数组

代码

include<stdio.h>
//对两个有序子数组进行融合
void merge(int Arr[],int L, int M,int R)
{
    int LEFT_SIZE = M - L + 1;
    int RIGHT_SIZE = R - M;
    int left[LEFT_SIZE];
    int right[RIGHT_SIZE];
    int i ;
    int j;
    for (i = 0;i < LEFT_SIZE;i++)
        left[i] = Arr[L+i];
    for(j = 0; j < RIGHT_SIZE; j++)
        right[j] = Arr[M+j+1];

    /*for (i = 0; i < RIGHT_SIZE;i++)
        printf("%d ",right[i]);
    printf("\n");
    */
    int k = L;
    i = 0;
    j = 0;
    while(i < LEFT_SIZE && j < RIGHT_SIZE)
    {
        if(left[i] < right[j])
        {
            Arr[k] = left[i];
            i++;
            k++;
        }
        else
        {
            Arr[k] = right[j];
            j++;
            k++;
        }
    }

    while(i<LEFT_SIZE)
    {
        Arr[k] = left[i];
        i++;
        k++;
    }
    while(j<RIGHT_SIZE)
    {
        Arr[k] = right[j];
        j++;
        k++;
    }


}
//递归
void merge_sort(int Arr[],int L,int R)
{
    if (L==R)
        return;
    else
    {
        int M = (L+R) / 2;
        merge_sort(Arr,L,M);
        merge_sort(Arr,M+1,R);
        merge(Arr,L,M,R);
    }


}

int main(void)
{
    int a[] = {2,1,4,0,3,5,2,3,12};
    int L = 0;
    int R = sizeof(a) / sizeof(int) - 1;
    merge_sort(a,L,R);
    int i;
    for (i=0;i <=R;i++)
        printf("%d\n",a[i]);
    printf("\n");
    return 0;
}