排序算法---合并排序（Merge Sort）

合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。

---

算法基本思想：

1. 首先将未排序的数组，进行拆分成n个单一的数据。
2. 然后将这n个数据按照索引顺序，两两组合、排序。（例如：有8个数据，那么第一个和第二个组合，第三个和第四个组合。。。如有未组合的数据这放任其暂时不管）
3. 将上面已经两两组合、排序好的数据看成是一个“元素”，再进行两两组合、排序。。。
4. 重复上述的步骤，最后就得到已经排序好的数组。

示意图

代码实现：

import java.util.Arrays;
import java.util.Date;

/**
 * Created by noonbiteun
 * Date: 2017/8/1
 */
public class MergeSort {
    private static void merge(int[] unsortArr, int frontIndex, int backIndex, int lastIndex, int[] sortArr) {
        int i = frontIndex;//前半段的起始索引
        int j = backIndex;//后半段的起始索引
        int k = 0;
        //合并两个小分组
        while (i < backIndex && j < lastIndex) {
            if (unsortArr[i] < unsortArr[j]) {
                sortArr[k++] = unsortArr[i++];
            } else {
                sortArr[k++] = unsortArr[j++];
            }
        }
        while (i < backIndex) {
            //前半段还有数据
            sortArr[k++] = unsortArr[i++];
        }
        while (j < lastIndex) {
            //后半段还有数据
            sortArr[k++] = unsortArr[j++];
        }
        for (int l = 0; l < k; l++) {
            //将排序好的数放回
            unsortArr[frontIndex + l] = sortArr[l];
        }
    }


    public static void sort(int[] arr, int first, int last, int[] sorted) {
        if (first < last - 1) {
            int back = (first + last) / 2;
            sort(arr, first, back, sorted);
            sort(arr, back, last, sorted);
            merge(arr, first, back, last, sorted);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[10];
        //初始化数组
        for (int i = 0; i < 10; i++) {
            arr[i] = (int) (Math.random() * (100 + 1));
        }
        long t1 = new Date().getTime();
        System.out.println("原始的顺序： "+ Arrays.toString(arr));
        MergeSort.sort(arr, 0, arr.length, new int[arr.length]);
        long t2 = new Date().getTime();
        System.out.println("排序后顺序： "+ Arrays.toString(arr));
        System.out.println("耗时："+(t2-t1)+" ms");
    }
}

输出结果：

运行结果

分析小结：

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。