归并排序

归并排序算法思想

所谓归并，就是将两个或两个以上的有序表合并成一个新的有序表。有两个已经排好序的有序表A[1]_A[n]和B[1]B[m]，通过归并把它们合成一个有序表C[1]~C[m+n]。

基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序算法实现

 private static int[] copy;

    public static void main(String[] args) {
        int[] arr = {3, 3, 3, 3, 3, 3, 4, 3};
        int lo = 0;
        int hi = arr.length - 1;
        //create copy array
        copy = new int[arr.length];
        mergeSortToTop(arr, lo, hi);
        mergeSortToButtom(arr);
        for (int i : arr) {
            System.out.print(i + "  ");
        }

    }

    /**
     * 自顶而上的归并排序
     *
     * @param arr
     * @return
     */
    private static void mergeSortToButtom(int[] arr) {
        int N = arr.length;
        for (int sz = 1; sz < N; sz = sz + sz) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }

        }
    }

    /**
     * 自顶而下的归并排序
     *
     * @param arr
     * @param lo
     * @param hi
     * @return
     */
    private static void mergeSortToTop(int[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) / 2;
        mergeSortToTop(arr, lo, mid);
        mergeSortToTop(arr, mid + 1, hi);
        merge(arr, lo, mid, hi);
    }

    /**
     *其实就是两个数组合并
     *
     * @param arr
     * @param lo
     * @param mid
     * @param hi
     */
    private static void merge(int[] arr, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;
        // 将原数组copy到新的数组里
        for (int k = lo; k <= hi; k++) {
            copy[k] = arr[k];
        }
        //分成两半进行排序
        for (int k = lo; k <= hi; k++) {
            if (i > mid) arr[k] = copy[j++];
            else if (j > hi) arr[k] = copy[i++];
            else if (arr[i] > arr[j]) arr[k] = copy[j++];
            else arr[k] = copy[i++];
        }
    }

算法复杂度

1.平均时间复杂度： O(NLogN)
2.最好情况时间复杂度： O(NLogN)
3.最差情况时间复杂度： O(NLogN)
4.所需要额外空间： O(N)

算法稳定性

1.归并排序算法是稳定的

想看完整版算法请点击：归并排序