排序算法(五) 归并排序

1.动图演示

1.1自顶向下的归并排序

2.代码实现

2.1自顶向下的归并排序

package sort;

import java.util.Arrays;
// 测试工具类在这里 https://www.cnblogs.com/paidaxing7090/p/15080493.html
import 测试工具类.SortTestHelper;

public class MergeSort {

    private MergeSort() {
    }

    public static void sort(Comparable[] arr, int l, int r) {
       if (l>=r) {return;}
        int middle = (l + r) / 2;  //注意l+r是否会溢出int
        sort(arr, l, middle);
        sort(arr, middle + 1, r);
        if (arr[middle].compareTo(arr[middle + 1]) > 0) { //当arr[middle] <= arr[middle+1] 则代表整个数组已经有序了，无须再次merge ,对于近乎有序的数组 排序会更快
            merge(arr, l, middle, r);                        //有序不处理，是常规操作。
        }
    }

    static void merge(Comparable[] arr, int l, int mid, int r) {

        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);//注意临时数组（空间换时间）  是从下标0开始的。后面用这个数组 要注意下标

        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        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].compareTo(aux[j - l]) < 0) {  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i - l];
                i++;
            } else {  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j - l];
                j++;
            }
        }
    }
    public static void sort(Comparable[] arr) {
        int n = arr.length;
        sort(arr, 0, n - 1);
    }

    public static void main(String[] args) {
        int N = 5000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        Integer[] arr4 = arr.clone();
        Integer[] arr3 = arr.clone();
        SortTestHelper.testSort("sort.MergeSort", arr);
        SortTestHelper.testSort("sort.MergeSort2", arr3);
        long l = System.currentTimeMillis();
        Arrays.sort(arr4);
        long l2 = System.currentTimeMillis();
        System.out.println("" + (l2 - l)+"ms");
        Integer[] arr2 = SortTestHelper.generateNearlyOrderedArray(N, 100);
        SortTestHelper.testSort("sort.MergeSort", arr2);
    }


}

2.2自底向上的归并排序

public class MergeSort2 {
		
		//自下而上 循环迭代的归并排序
		//排序过程没有使用数组的 定位数据，这个性质 使得该排序对链表排序 非常快
		public static void sort(Comparable[] arr ) {
			int n=arr.length;
			for(int sz=1 ; sz<=n;sz+=sz)
				for (int i = 0; i +sz < n; i+=sz+sz) {
					if(arr[i+sz-1].compareTo(arr[i+sz])>0)
					MergeSort.merge(arr,i,i+sz-1, Math.min(i+sz+sz-1,n-1)     );
				}

}

3.测试结果

4.结论

关键就是merge方法。