数据结构（十一）：归并排序

青旅半醒 2021-09-10 06:14 458阅读 0赞

*  利用递归与分治技术将数据序列划分成越来越小的半子表，在对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列

### 直接插入排序例子 ###

*  流程：
    
     *  分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素
     *  治理: 对每个子序列分别调用归并排序 MergeSort
     *  合并: 合并两个排好序的子序列,生成排序结果
 *  举例：
    
    ![9434708-45cb923ad13a31c6][]
    
    归并排序

### 直接插入排序代码 ###

public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
        System.out.println(Arrays.toString(temp));
    }
    
    public static void mergeSort(int[] a, int[] tmp, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(a, tmp, left, mid);       // 左排序
            mergeSort(a, tmp, mid + 1, right);      // 右排序
            merge(a, tmp, left, mid + 1, right);        // 左右合并
        }
    }
    
    public static void merge(int[] a, int[] tmp, int left, int rightPos, int right) {
        int leftEnd = rightPos - 1;
        int tmpPos = left;
        int num = right - left + 1;
        while (left <= leftEnd && rightPos <= right) {
            if (a[left] < a[rightPos]) {
                tmp[tmpPos++] = a[left++];
            } else {
                tmp[tmpPos++] = a[rightPos++];
            }
        }
        while (left <= leftEnd) {
            tmp[tmpPos++] = a[left++];
        }
        while (rightPos <= right) {
            tmp[tmpPos++] = a[rightPos++];
        }
        for (int i = 0; i < num; i++, right--) {
            a[right] = tmp[right];
        }
    }

### 归并排序性能 ###

*  归并排序是一种稳定的排序
 *  归并排序利用了完全二叉树深度是 log₂ⁿ+1 的特性，因此效率较高
 *  一趟归并需要将数组 a\[\] 中相邻的长度为 h 的有序序列进行两两归并.并将结果放到 temp\[\] 中，这需要将待排序列中的所有记录扫描一遍，因此耗费O(n)
 *  而完全二叉树的深度可知，整个归并排序需要进行 log₂ⁿ 次，因此总的时间复杂度为 O(nlogn)，而且这是归并排序算法中最好、最坏、平均的时间性能
 *  需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序

[9434708-45cb923ad13a31c6]: /images/20210811/c577654f6d73415982a36cc36172b1bb.png