java归并排序

冷不防 2021-12-13 02:55 248阅读 0赞

# 归并排序 稳定性：稳定 #

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

# 归并排序 #

##    基本思想 ##

归并排序就是利用归并的思想实现的排序方法。而且充分利用了完全二叉树的深度是的特性，因此效率比较高。其基本原理如下：对于给定的一组记录，利用递归与分治技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。

经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录并与第二个位置记录交换；重复该过程，知道进行比较的记录只剩下一个为止。

工作原理：

（1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置

（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

（4）重复步骤3直到某一指针达到序列尾

（5）将另一序列剩下的所有元素直接复制到合并序列尾

**算法分析**  
一趟归并需要将数组 a\[\]中相邻的长度为h的有序序列进行两两归并.并将结果放到temp\[\]中，这需要将待排序列中的所有记录扫描一遍，因此耗费O(n)，而又完全二叉树的深度可知，整个归并排序需要进行（）次，因此总的时间复杂度为O(nlogn)，而且这是归并排序算法中最好、最坏、平均的时间性能。

由于归并排序在归并过程中需要与原始序列同样数量的存储空间存放归并结果以及递归时深度为的栈空间，因此空间复杂度为O(n+logn).

另外，对代码进行仔细研究，发现merge函数中有if (a\[i\] < a\[j\]) 的语句，说明它需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。

也就是说，归并排序是一种比较占内存，但却效率高且稳定的算法。Java实现

/**
    
     * 归并排序
    
     * @param data
    
     * @param low
    
     * @param mid
    
     * @param high
    
     */
    
    public static voidmerge(int[] data, int low, int mid, int high) {
    
        int[] temp = new int[high - low + 1];
    
        int i= low;// 左指针
    
        int j = mid + 1;// 右指针
    
        int k = 0;
    
        // 把较小的数先移到新数组中
    
        while (i <= mid && j <= high){
    
            if (data[i] < data[j]) {
    
                temp[k++] = data[i++];
    
            } else {
    
                temp[k++] = data[j++];
    
            }
    
        }
    
        // 把左边剩余的数移入数组
    
        while (i <= mid) {
    
            temp[k++] = data[i++];
    
        }
    
        // 把右边边剩余的数移入数组
    
        while (j <= high) {
    
            temp[k++] = data[j++];
    
        }
    
        // 把新数组中的数覆盖nums数组
    
        for (int k2 = 0; k2 < temp.length; k2++){
    
            data[k2 + low] = temp[k2];
    
        }
    
    }
    
    /**
    
     * 归并排序
    
     * 时间复杂度：O(nlog2n)
    
     * @param data
    
     * @param low
    
     * @param high
    
     */
    
    public static voidmergeSort(int[] data, int low, int high) {
    
        int mid = (low + high) / 2;
    
        if (low < high) {
    
            mergeSort(data, low, mid);//左边
    
            mergeSort(data, mid + 1, high);//右边
    
            merge(data, low, mid, high);//左右归并
    
        }
    
    }