归并排序算法、时间复杂度和稳定性

客官°小女子只卖身不卖艺 2022-05-17 06:17 225阅读 0赞

## 归并排序 ##

### 算法原理 ###

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

### 算法分析 ###

排序的思想就是将元素无限拆分，直到无可拆分为止，再将拆分的元素两两按序合并。

归并排序的原理可以通过下面这张图看清楚：

![归并排序][E5_BD_92_E5_B9_B6_E6_8E_92_E5_BA_8F.png]

### 代码实现 ###

/** * @Title: mergeSort * @Description: 归并排序 * @param: array * void @throws */
    public static void mergeSort(int[] array) {
        int[] temp = new int[array.length];
        sort(array, temp, 0, array.length - 1);
    }
    
    /** * @Title: sort * @Description: 使用归并排序，对array的left~right进行排序 * @param: array * @param: temp * @param: left * @param: right */
    private static void sort(int[] array, int[] temp, int left, int right) {
        // 定义待排序中间元素
        int mid = (left + right) / 2;
        if (left < mid) {
            // 递归排序中间元素及左边的元素
            sort(array, temp, left, mid);
        }
        if (mid + 1 < right) {
            // 递归排序中间元素右边的元素
            sort(array, temp, mid + 1, right);
        }
        // 合并左右两边的元素
        merge(array, temp, left, mid, right);
    }
    
    /** * @Title: merge * @Description: 借助temp数组，合并mid元素左右的元素 * @param: array * @param: temp * @param: left * @param: mid * @param: right */
    private static void merge(int[] array, int[] temp, int left, int mid, int right) {
        // 用于遍历左边元素
        int i = left;
        // 用于遍历右边元素
        int j = mid + 1;
        // 临时变量
        int t = 0;
        while (i <= mid && j <= right) {
            // 将左右两边最小的元素添加到temp数组中
            if (array[i] <= array[j]) {
                temp[t++] = array[i++];
            } else {
                temp[t++] = array[j++];
            }
        }
    
        while (i <= mid) {
            // 将左边剩余元素添加到temp数组中
            temp[t++] = array[i++];
        }
        while (j <= right) {
            // 将右边剩余元素添加到temp数组中
            temp[t++] = array[j++];
        }
        t = 0;
        // 将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            array[left++] = temp[t++];
        }
    }  array[j] = temp;

### 时间复杂度和算法稳定性 ###

从上面的代码中可以看出每次合并操作的时间复杂度是O(N)，而二叉树的深度是log2N，所以总的时间复杂度是O(N\*lgN)。

因为在合并的时候，如果两个数相等，可以将前面的数先放到辅助数组中，所以归并排序是稳定的。

## 相关代码都在github上:[https://github.com/LebronChenX/sort][https_github.com_LebronChenX_sort] ##

喜欢这篇文章的朋友，欢迎长按下图关注公众号**lebronchen**，第一时间收到更新内容。  
![扫码关注][70]

[E5_BD_92_E5_B9_B6_E6_8E_92_E5_BA_8F.png]: /images/20220517/36f685ff0efa4879b39dba23c579c8d7.png
[https_github.com_LebronChenX_sort]: https://github.com/LebronChenX/sort
[70]: /images/20220517/e8e90da0a94f417397a18128bbd5d06d.png