TIP

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并排序是一种稳定的排序方法。

img

最重要的可能需要处理的是将两个有序数组合并为一个有序数组

# 代码实现

public void mergeSort(int[] arr, int n) {
    subMergeSort(arr, 0, n - 1);
}

// 递归使用归并排序,对 arr[l...r] 的范围进行排序
private void subMergeSort(int[] arr, int l, int r) {
    if(l >= r)
        return;

    int mid = l + (r - l) / 2;
    subMergeSort(arr, l, mid);
    subMergeSort(arr, mid + 1, r);

    // 对已经有序的两部分进行归并
    merge(arr, l, mid, r);
}


// 将 arr[l...mid] 和 arr[mid+1...r] 两部分进行归并
private void merge(int[] arr, int l, int mid, int r) {
    // 辅助排序的数组
    int[] aux = new int[r - l + 1];
    for (int i = l; i <= r; i++)
        aux[i - l] = arr[i];

    int i = l, j = mid + 1;
    for (int k = l; k <= r; k ++) {
        if (i > mid) {
            arr[k] = aux[j - l];
            j ++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i ++;
        } else if (aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
            i ++;
        } else {
            arr[k] = aux[j - l];
            j ++;
        }
    }
}

# 归并排序的两个优化

  • 在元素比较小的时候,其实这个时候更多的时候元素可能大部分都是有序的,所以这个时候可以引入【插入排序】这时可能整体的效率会更高

  • 归并的前提 更多的是两个子数组是无序的,如有第二个数组的第一个元素,已经大于第一个数组的最后一个元素,就没有必要再进行归并过程了

    // 对已经有序的两部分进行归并, 只有当满足上面所说的条件再排序
    if (arr[mid + 1] < arr[mid])
    	merge(arr, l, mid, r);
    
最后编辑时间: 4/27/2020, 10:23:03 PM