排序算法——归并排序

原理

归并排序的基础是合并有序数组，运用了分治的思想，将数组对半分，递归，直到两个数组长度都为1，可以看作两个有序数组，然后将其合并，在递归处得到长度更大的有序数组，再合并。

复杂度分析

平均时间复杂度为O(n㏒₂n)
时间复杂度最坏为O(n㏒₂n)
空间复杂度为 O(n+㏒₂n)，临时数组+递归所需栈空间
稳定。网上有空间复杂度为O(1)的实现，暂时还没研究。

代码实现

合并有序数组的实现

/**
 * 合并两个有序数组
 **/
private void mergeSortedArr(int a[], int b[], int c[]){
    int i=0;
    int j=0;
    int k=0;
    while (i < a.length && b < j.length){
        if (a[i] < b[j]) {
            c[k++] = a[i++];
        } else{
            c[k++] = b[j++];
        }
    }
    while (i < a.length){
        c[k++] = a[i++];
    }
    while (j < b.length){
        c[k++] = b[j++];
    }
}

归并排序实现

/**
 * 归并排序
 * 合并两个有序数组，分治思想
 **/

public void sort(int[] a){
    mergeSort(a, 0, a.length - 1, new int[a.length]);
}

private void mergeSort(int[] a, int start, int end, int[] tmp){
    if (start >= end) {//递归出口
        return ;
    }
    int middle = (start + end)/2;
    mergeSort(a, start, middle, tmp);//左边有序
    mergeSort(a, middle, end, tmp);//右边有序
    stepSort(a, start, middle, end, tmp);//合并两个有序数组
}

private void stepSort(int[] a, int start, int middle, int end, int[] tmp){
    int i = start;
    int j = middle;
    int k = 0;
    while (i <= middle && j < end){
        if (a[i] < a[j]) {
            tmp[k++] = a[i++];
        } else{
            tmp[k++] = a[j++];
        }
    }
    while (i <= middle){
        tmp[k++] = a[i++];
    }
    while (j < end){
        tmp[k++] = a[j++];
    }
    //结果写回数据源
    for (i = 0; i < k; i++) {
        a[i + start] = tmp[i];
    }
}