归并排序

基本思想:

将两个有序表合并成一个有序表。

归并排序.gif

归并排序示例:

代码：

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] s = { 49, 38, 65, 97, 76, 13, 27, 49 };
        new MergeSort().mergeSort(s, 0, s.length - 1);

        for (int i = 0; i < s.length; i++) {
            System.out.printf("%d ", s[i]);
        }
    }

    void mergeSort(int s[], int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(s, start, mid);
            mergeSort(s, mid + 1, end);
            merge(s, start, mid, end);

        }

    }

    void merge(int s[], int start, int mid, int end) {

        int[] temp = new int[s.length];

        int p1 = start, p2 = mid + 1, k = start;

        while (p1 <= mid && p2 <= end) {
            if (s[p1] <= s[p2]) {
                temp[k++] = s[p1++];

            } else {
                temp[k++] = s[p2++];
            }
        }

        while (p1 <= mid) {
            temp[k++] = s[p1++];
        }
        while (p2 <= end) {
            temp[k++] = s[p2++];

        }

        for (int i = start; i <= end; i++) {
            s[i] = temp[i];
        }
    }

输出：

13 27 38 49 49 65 76 97 

归并排序的效率分析

排序算法	平均时间性能	最好时间性能	最坏时间性能	辅助空间	稳定性
归并排序					稳定

• 归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。对 n个元素的表，将这n个元素看作叶结点，若将两两归并生成的子表看作它们的父结点，则归并过程对应由叶向根生成一棵二叉树的过程。所以归并趟数等于二叉数的高度减1，即⎣log₂n⎦。每一趟归并需移动 n个元素，即每一趟归并的时间复杂度为O(n)。因此，2-路归并排序的时间复杂度为O(nlog₂n)。
• 利用归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的空间复杂度为O(n)，比前面介绍的其它排序方法占用的空间大。
• 由于归并排序中，每两个有序表合并成一个有序表时，若分别在两个有序表中出现有相同排序码，则会使前一个有序表中相同排序码先复制，后一有序表中相同排序码后复制，从而保持它们的相对次序不会改变。所以，归并排序是一种稳定的排序方法。