归并排序.md

归并排序

定义

建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用，且各层分治递归可以同时进行。

• 分解 - 分解待排序的n个元素的序列成各具n / 2个元素的两个子序列。
• 解决 - 使用归并排序递归地排序两个子序列
• 合并 - 合并两个已排序的子序列

Java源码中的实现（没有完全理解）

private static final int INSERTIONSORT_THRESHOLD = 7;

/**
     * Src is the source array that starts at index 0
     * Dest is the (possibly larger) array destination with a possible offset
     * low is the index in dest to start sorting
     * high is the end index in dest to end sorting
     * off is the offset to generate corresponding low, high in src
     * To be removed in a future release.
     */
private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;


        // Insertion sort on smallest arrays
        // 如果长度小于阈值(7)，直接使用冒泡排序
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        //如果已经排好序，则直接从src复制到dest中即可
        // If list is already sorted, just copy from src to dest.  This is an
        // optimization(优化) that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            //这里很巧妙，首先判断第二个数组是否已经全部放入目的数组，如果是的话，直接把第一个数组的元素放入目的数组
            //然后判断，第一个数组是否已经全部放入目的数组，如果是的话，直接把第二个数组的元素放入目的数组
            //上面两个判断直接就避免了数组越界问题
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

实现

public class MergeSort {
    private static <T> void mergeSort(T[] srcArray, T[] destArray, int low, int high, JComparable<T> comparable) {
        int length = high - low;
        if (length < 3) {//长度不超过3的，使用插入排序
            InsertSort.sort(srcArray, comparable);  
            return;
        }
        int destLow = low;
        int destHeight = high;
        int mid = (low + high) >>> 1;
        mergeSort(srcArray, destArray, low, mid, comparable);
        mergeSort(srcArray, destArray, mid, high, comparable);
        for (int i = destLow, p = low, q = mid; i < destHeight; i++) {
            if (q >= high || p < mid && comparable.moreThan(srcArray[p], srcArray[q])) {
                destArray[i] = srcArray[q++];
            } else {
                destArray[i] = srcArray[p++];
            }
        }
    }

    public static <T> void sort(T[] srcArray, T[] destArray, JComparable<T> comparable) {
        mergeSort(srcArray, destArray, 0, srcArray.length, comparable);
    }

}

测试

public static void main(String[] args) {
    Integer[] array = new Integer[]{5, 2, 4, 6, 1, 3};
    Integer[] dest = new Integer[6];
    MergeSort.sort(array, dest, new IntegerComparable());
    for (int i = 0; i < dest.length; i++) {
        System.out.print(dest[i] + "\t");
    }
}

1 2 3 4 5 6

时间复杂度

O(n * log(n))