Java实现归并排序

发布于 2021-07-31  64 次阅读


算是理解递归了,分治 ,现在无法理解大话数据结构的归并排序,感觉很乱

下图递归值的变化,一步一步理解。

package com.apesblog.sort.merge;

public class Merge {
    private static Comparable[] assist;

    public static void sort(Comparable[] a) {
        assist = new Comparable[a.length];
        int lo = 0;
        int hi = a.length - 1;
        sort(a, lo, hi);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = (lo + hi) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo;
        int j = lo;
        int k = mid + 1;
        while (j <= mid && k <= hi) {
            if (less(a[j], a[k])) {
                assist[i++] = a[j++];
            } else {
                assist[i++] = a[k++];
            }
        }
        while (j <= mid) {
            assist[i++] = a[j++];
        }
        while (k <= hi) {
            assist[i++] = a[k++];
        }
        for (int index = lo; index <= hi; index++) {
            a[index] = assist[index];
        }
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}
package com.apesblog.sort.merge;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        Integer[] a = { 8, 4, 5, 7, 1, 3, 6, 2 };
        Merge.sort(a);
        System.out.println("归并排序:" + Arrays.toString(a));

        String[] str = { "d", "e", "f", "c", "b", "a" };
        Merge.sort(str);
        System.out.println("归并排序:" + Arrays.toString(str));

    }

}