归并排序-merge递归

merge sort

image

用到递归的思想
分成两半进行排序，把结果进行合并(merge),再分成两半进行排序，一直这样递归下去。

递归(recursion)

时间和空间消耗比较大。每一次函数调用都需要在内存栈中分配空间以保存参数，返回地址以及临时变量，而且往栈里面压入数据和弹出都需要时间。

要注意basecase，终止条件

对一个数组前半部和后半部都是排过序的进行合并

void merge(int array[], int leftpos, int rightpos, int lastpos)
{
    int* temparray = (int* )malloc(sizeof(int)*(lastpos - leftpos + 1));
    int i = leftpos;
    int j = rightpos;
    int k = 0;
    while((i<rightpos)&&(j<=lastpos)  ){
        if(array[i] <= array[j])
            temparray[k++] = array[i++];
        else
            temparray[k++] = array[j++];
    }
    while(i<rightpos)
        temparray[k++] = array[i++];
    while(j<=lastpos)
        temparray[k++] = array[j++];    
    
    for(i=0;i<=lastpos-leftpos;i++)
    {
        array[leftpos+i] = temparray[i]; 
    }
    free(temparray);
}

把数组分为两半，前半段排序，后半段排序，合并

void recursionmerge(int array[],int left, int right)
{
    if(left == right ) 
        return;
    int mid = (right+left)/2;

    recursionmerge(array,left,mid);
    recursionmerge(array,mid+1,right);
    merge(array,left,mid+1,right);
}

时间复杂度

平均，最好，最坏 O(N*log2N)

不断分成两半（分的次数就是对数log2N， 每次又是N 所以就是N*log2N)。

空间复杂度
O(N)

稳定, Java对象的排序使用mergesort. 改进版叫TimSort.