排序算法

1、归并排序

归并是把两个或两个以上有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的，然后把有序子序列合并为整体有序序列。

注意：在递归中必须传入(low, middle)和(middle+1, high)，而快排的递归中可以是(low, middle - 1)和(middle+1, high)

递归实现：

public void merge(int[] arr) {
    if (arr == null || arr.length == 0)
        return;
    int[] copy = new int[arr.length];
    mergeSort(arr, copy, 0, arr.length - 1);
}

private void mergeSort(int[] arr, int[] copy, int low, int high) {
    if (low == high)
        return;
    int mid = (low + high) / 2;
    mergeSort(arr, copy, low, mid);
    mergeSort(arr, copy, mid + 1, high);
    int i = mid;
    int j = high;
    int locCopy = high;
    while (i >= low && j > mid) {
        if (arr[i] > arr[j])
            copy[locCopy--] = arr[i--];
        else
            copy[locCopy--] = arr[j--];
    }
    while (i >= low) {
        copy[locCopy--] = arr[i--];
    }
    while (j > mid) {
        copy[locCopy--] = arr[j--];
    }
    for (int k = low; k <= high; k++) {
        arr[k] = copy[k];
    }
}

非递归实现：

public void mergeSort(int[] arr) {
    int len = 1;
    while (len < arr.length) {
        for (int i = 0; i < arr.length; i += 2 *len) {
            merge(arr, i, len);
        }
        len *= 2;
    }
}

public void merge(int[] arr, int i, int len) {
    int start = i;
    int lenI = i + len;
    int j = i + len;
    int lenJ = j + len;
    int[] temp = new int[len * 2];
    int count = 0;
    while (i < lenI && j < lenJ && j < arr.length) {
        if (arr[i] <= arr[j]) {
            temp[count++] = arr[i++];
        } else {
            temp[count++] = arr[j++];
        }
    }
    while (i < lenI && i < arr.length) {
        temp[count++] = arr[i++];
    }
    while (j < lenJ && j < arr.length) {
        temp[count++] = arr[j++];
    }
    count = 0;
    while (start < j && start < arr.length) {
        arr[start++] = temp[count++];
    }
}