5.归并排序法(自顶向下)

归并过程

归并排序无法原地完成！

每次只比较a中最小的元素和b中最小的元素，谁更小就把谁拿出来。


复制一份原数组出来，比较i与j

Merge过程

我们申请一个临时数组 tmp，大小与 A[p…r]相同。我们用两个游标 i 和 j，分别指向 A[p…q]和 A[q+1…r]的第一个元素。比较这两个元素 A[i]和 A[j]，如果 A[i]<=A[j]，我们就把 A[i]放入到临时数组 tmp，并且 i 后移一位，否则将 A[j]放入到数组 tmp，j 后移一位。

package com.hoho.algorithms.sort.mergesort;
import com.hoho.algorithms.api.ArrayGenerator;
import com.hoho.algorithms.api.SortingHelper;
import com.hoho.algorithms.basesort.InsertSort;
import java.util.Arrays;
import java.util.SortedMap;
public class MergeSort {
    private MergeSort() {
    }
    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
    /**
     * 合并两个有序的数组 arr[l,mid] 与 arr[mid+1,r]
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
        //Arrays.copyOfRange(T[ ] original,int from,int to),包括from，不包括to
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int i = l;
        int j = mid + 1;
        //每轮循环为arr[k]赋值
        for (int k = l; k <= r; k++) {
            //判断i与j是否越界
            if (i > mid) {
                //i越界
                //j-l: arr数组是从l开始的，temp数组是从0开始的，所以要用j-l表示j在temp中的位置
                arr[k] = temp[j - l];
                j++;
            } else if (j > r) {
                //j越界
                arr[k] = temp[i - l];
                i++;
            } else {
                //都没有越界
                if (temp[i - l].compareTo(temp[j - l]) <= 0) {
                    arr[k] = temp[i - l];
                    i++;
                } else {
                    arr[k] = temp[j - l];
                    j++;
                }
            }
        }
    }
}