题目描述

归并排序

样例

1≤n≤100000

输入样例：

5
3 1 2 4 5
输出样例：

1 2 3 4 5

算法1

(方法一) $O(nlgn)$

创建一个跟原数组长度一样的临时数组，给原数组设置两个指针，
一个指向第一个元素，一个指向中间元素，依次比较两个指针对应的元素大小，
根据大小依次放入临时数组，最后将临时数组的值依次赋值给原数组

时间复杂度

参考文献

Java代码

public static void mergeSort(int a[], int low, int high){
    int []temp=new int[high-low+1];
    int mid=(low+high)/2;
    if(low>=high){
        return;
    }
    mergeSort(a,low,mid);
    mergeSort(a,mid+1,high);
    int i=low,j=mid+1,k=0;
    while ((i<=mid)&&(j<=high)){
        if(a[i]<=a[j]){
            temp[k++]=a[i++];
        }
        else {
            temp[k++]=a[j++];
        }
    }
    while (i<=mid) temp[k++]=a[i++];
    while (j<=high) temp[k++]=a[j++];
    for(i=low,j=0;i<=high;i++,j++){
        a[i]=temp[j];
    }
}

算法2

(方法二) $O(nlgn)$

创建AB两个数组，A数组里面的值为原数组左边的值，B数组里面的值为原数组右边的值
再分别给AB两个数组增加一个元素为∞，当作哨兵，然后依次比较AB数组的值，小的放到原数组的位置

时间复杂度

参考文献

java 代码

public static void mergesort(int a[],int low,int high) {
int mid=(high+low)/2;
if(low>=high){
return;
}
mergesort(a,low,mid);
mergesort(a,mid+1,high);
int len=high-low+1;
int ll=mid-low+1;
int lr=len-ll;
int []b=new int[ll+1];
int []c=new int[lr+1];
b[ll]=10000;
c[lr]=10000;
for (int i = 0; i <ll; i) {
b[i]=a[low+i];
}
for (int i = 0; i <lr; i) {
c[i]=a[mid+1+i];
}
for (int i = low,j=0,k=0; i <=high; i) {
if(b[j]<=c[k]){
a[i]=b[j];
}
else {
a[i]=c[k++];
}
}

}