Contents

1. 1. 主要就是经典的分治法思想

主要就是经典的分治法思想

可以参考下《算法导论》，里面给了比较详细的图解

#include<stdio.h>
int a[10000], b[10000];

void mergearray(int a[], int first, int mid, int last, int temp[])//temp数组用于临时储存另外一组数{

    int i = first, j = mid + 1;
    int k = 0;
    while(i <= mid && j <= last)  //第一组数的最后和第二组数的最后
    {
        if(a[i] <= a[j])
            temp[k++] = a[i++];  
        else
            temp[k++] = a[j++];  
    }
    while(i <= mid)
        temp[k++] = a[i++];    
    while(j <= last)
        temp[k++] = a[j++];     
    for(i = 0; i < k; i++)
        a[first + i] = temp[i];
}

void mergesort(int a[], int first, int last, int temp[]){

    if(first < last)  //注意这个判断，直到fist==last，把整体分为了最小的单元
    {
        int mid = (first + last) / 2;   //注意是向下取整 ,所以后面才是mid+1
        mergesort(a, first, mid, temp);  //左边有序
        mergesort(a, mid + 1, last, temp); //右边有序
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    }//用递归实现将数组拆分成一个个元素，然后将两个两个的组合起来
}

int main(){

    int n, i;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%d", &a[i]);
    mergesort(a, 0, n-1, b);
    for(i = 0; i < n; i++)
        printf("%d ",a[i]);
    return 0;
}