归并排序Java详细推演和实现-数据结构和算法-09-排序

归并排序

  归并” 一词的中文含义就是合并、并入的意思，而在数据结构中的定义是将两个 或两个以上的有序表组合成一个新的有序表。
  归并排序(Merging Sort)就是利用归并的思想实现的排序方法。它的原理是假 设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为 1,然后两两归并，得到［n/2] (［x］表示不小于x的最小整数)个长度为2或1的有 序子序列；再两两归并，……,如此重复，直至得到一个长度为n的有序序列为止， 这种排序方法称为2路归并排序。

推演 归并递归方式

归并非递归方式

递归方式的运行追踪

自己可以推演下。。。

[50, 10, 0, 0, 0, 0, 0, 0, 0]
[10, 50, 0, 0, 0, 0, 0, 0, 0]
[10, 50, 0, 0, 0, 0, 0, 0, 0]

[10, 50, 90, 0, 0, 0, 0, 0, 0]
[10, 50, 90, 0, 0, 0, 0, 0, 0]
[10, 50, 90, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 30, 70, 0, 0, 0, 0]
[0, 0, 0, 30, 70, 0, 0, 0, 0]
[10, 50, 90, 30, 70, 0, 0, 0, 0]

[10, 50, 90, 30, 70, 0, 0, 0, 0]
[10, 30, 50, 70, 90, 0, 0, 0, 0]
[10, 30, 50, 70, 90, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 40, 80, 0, 0]
[0, 0, 0, 0, 0, 40, 80, 0, 0]
[10, 30, 50, 70, 90, 40, 80, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 60, 20]
[0, 0, 0, 0, 0, 0, 0, 20, 60]
[10, 30, 50, 70, 90, 40, 80, 20, 60]

[0, 0, 0, 0, 0, 40, 80, 20, 60]
[0, 0, 0, 0, 0, 20, 40, 60, 80]
[10, 30, 50, 70, 90, 20, 40, 60, 80]

[10, 30, 50, 70, 90, 20, 40, 60, 80]
[10, 20, 30, 40, 50, 60, 70, 80, 90]
[10, 20, 30, 40, 50, 60, 70, 80, 90]

非递归方式追踪

[50, 10, 0, 0, 0, 0, 0, 0, 0]
[10, 50, 0, 0, 0, 0, 0, 0, 0]
[10, 50, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 90, 30, 0, 0, 0, 0, 0]
[0, 0, 30, 90, 0, 0, 0, 0, 0]
[10, 50, 30, 90, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 70, 40, 0, 0, 0]
[0, 0, 0, 0, 40, 70, 0, 0, 0]
[10, 50, 30, 90, 40, 70, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 80, 60, 0]
[0, 0, 0, 0, 0, 0, 60, 80, 0]
[10, 50, 30, 90, 40, 70, 60, 80, 0]

[0, 0, 0, 0, 0, 0, 0, 0, 20]
[0, 0, 0, 0, 0, 0, 0, 0, 20]
[10, 50, 30, 90, 40, 70, 60, 80, 20]

[10, 50, 30, 90, 0, 0, 0, 0, 0]
[10, 30, 50, 90, 0, 0, 0, 0, 0]
[10, 30, 50, 90, 40, 70, 60, 80, 20]

[0, 0, 0, 0, 40, 70, 60, 80, 0]
[0, 0, 0, 0, 40, 60, 70, 80, 0]
[10, 30, 50, 90, 40, 60, 70, 80, 20]

[10, 30, 50, 90, 40, 60, 70, 80, 0]
[10, 30, 40, 50, 60, 70, 80, 90, 0]
[10, 30, 40, 50, 60, 70, 80, 90, 20]

[10, 30, 40, 50, 60, 70, 80, 90, 20]
[10, 20, 30, 40, 50, 60, 70, 80, 90]
[10, 20, 30, 40, 50, 60, 70, 80, 90]

归并递归-非递归实现

package com.my.data.structure;

import java.util.Arrays;

/**
 * 归并排序
 * 递归和非递归实现
 * 归并” 一词的中文含义就是合并、并入的意思，而在数据结构中的定义是将两个 或两个以上的有序表组合成一个新的有序表。
 */
public class MergeSort {
    public static int allArr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    public static int restArr[] = new int[allArr.length];

    /**
     * 归并排序-递归方式
     * @param sr 原始数组
     */
    private static void mSortRecursion(int[] sr) {
        int[] tr = new int[allArr.length];
        mSort(sr, tr, 0, allArr.length - 1);
    }

    /**
     * @param sr   原始数组
     * @param tr   临时数组
     * @param low  数组索引
     * @param high 数据索引
     */
    private static void mSort(int[] sr, int[] tr, int low, int high) {
        int mid = (low + high) / 2;
        if (low == high) {
            tr[low] = sr[low];
        } else {
            mSort(sr, tr, low, mid);            //左拆分
            mSort(sr, tr, mid + 1, high);   //右拆分
            merge(sr, tr, low, mid, high);       //排序归并
        }
    }

    private static void merge(int[] sr, int[] tr, int low, int mid, int high) {
        int i = low;
        int j = mid + 1;
        int k = 0;

        //记录过程数据
        int[] rest = new int[sr.length];
        System.out.println();
        for (int l = 0; l < high - low + 1; l++) {
            rest[l + low] = sr[l + low];
        }
        System.out.println(Arrays.toString(rest));

        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (sr[i] < sr[j]) {
                tr[k++] = sr[i++];
            } else {
                tr[k++] = sr[j++];
            }
        }

        // 把左边剩余的数移入数组
        while (i <= mid) {
            tr[k++] = sr[i++];
        }

        // 把右边边剩余的数移入数组
        while (j <= high) {
            tr[k++] = sr[j++];
        }

        // 把新数组中的数覆盖sr数组
        for (int l = 0; l < high - low + 1; l++) {
            sr[l + low] = tr[l];
            restArr[l + low] = tr[l];
            rest[l + low] = tr[l];
        }
        System.out.println(Arrays.toString(rest));
        System.out.println(Arrays.toString(restArr));
    }

    /**
     * 归并排序-非递归实现
     * @param sr 原始数组
     */
    private static void mSortNoRecursion(int[] sr) {
        int[] tr = new int[sr.length];
        int k = 1;
        while (k <= sr.length) {
            mergeNoRecursion(sr, tr, k - 1, sr.length - 1);
            //增量因子
            k = 2 * k;
        }

    }

    private static void mergeNoRecursion(int[] sr, int[] tr, int low, int high) {
        int i = 0;

        /*两两归并*/
        while (i <= high - 2 * (low + 1) + 1) {
            merge(sr, tr, i, i + low, i + 2 * low + 1);
            i = i + 2 * (low + 1);
        }

        /*归并最后的序列*/
        if (i < high - low + 1) merge(sr, tr, i, i + low, high);
    }

    public static void main(String[] args) {
        //递归实现方式
        mSortRecursion(allArr);
        //非递归实现方式
        //mSortNoRecursion(allArr);

    }

}

归并排序复杂度分析

我们来分析一下归并排序的时间复杂度，一趟归并需要将SR[l]^SR[n]中相邻的 长度为h的有序序列进行两两归并。并将结果放到TR[1]〜TR[n]中，这需要将待排 序序列中的所有记录扫描一遍，因此耗费。O(n)时间，而由完全二叉树的深度可知，整 个归并排序需要进行log2n次，因此，总的时间复杂度为O(nlogn)，而且这是归并排 序算法中最好、最坏、平均的时间性能。
由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结 果以及递归时深度为log2n的栈空间，因此空间复杂度为O(n+logn)
另外，对代码进行仔细研究，发现Merge函数中有if (SR[i] 也就是说，归并排序是一种比较占用内存，但却效率高且稳定的算法。

归并排序非递归实现

非递归的迭代方法，避免了递归时深度为log2n的栈空间，空间只是用到申请归并 临时用的TR数组，因此空间复杂度为O(n)，并且避免递归也在时间性能上有一定的 提升，应该说，使用归并排序时，尽量考虑用非递归方法。