数据结构-十大经典排序算法之归并排序

以你之姓@ 2023-02-21 06:37 88阅读 0赞

### 文章目录 ###

*  图示过程
 *   *  排序流程
     *  合并数组
     *  动图演示
     *  代码演示
     *  复杂度分析
     *   *  时间复杂度
         *  空间复杂度
     *  稳定性

# 图示过程 #

## 排序流程 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NTVV9oamg_size_16_color_FFFFFF_t_70]

## 合并数组 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NTVV9oamg_size_16_color_FFFFFF_t_70 1]

## 动图演示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NTVV9oamg_size_16_color_FFFFFF_t_70 2]

## 代码演示 ##

public static void mergeSort(int[] arr) {
        
        sort(arr, 0, arr.length - 1);
    }
    
    public static void sort(int[] arr, int L, int R) {
        
        if(L == R) {
        
            return;
        }
        int mid = L + ((R - L) >> 1);
        sort(arr, L, mid);
        sort(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }
    
    public static void merge(int[] arr, int L, int mid, int R) {
        
        int[] temp = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;
        // 比较左右两部分的元素，哪个小，把那个元素填入temp中
        while(p1 <= mid && p2 <= R) {
        
            temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 上面的循环退出后，把剩余的元素依次填入到temp中
        // 以下两个while只有一个会执行
        while(p1 <= mid) {
        
            temp[i++] = arr[p1++];
        }
        while(p2 <= R) {
        
            temp[i++] = arr[p2++];
        }
        // 把最终的排序的结果复制给原数组
        for(i = 0; i < temp.length; i++) {
        
            arr[L + i] = temp[i];
        }
    }

## 复杂度分析 ##

### 时间复杂度 ###

O(nlogn)

### 空间复杂度 ###

O(N)，归并排序需要一个与原数组相同长度的数组做辅助来排序

## 稳定性 ##

归并排序是稳定的排序算法，temp\[i++\] = arr\[p1\] <= arr\[p2\] ? arr\[p1++\] : arr\[p2++\];这行代码可以保证当左右两部分的值相等的时候，先复制左边的值，这样可以保证值相等的时候两个元素的相对位置不变

转载自：https://www.jianshu.com/p/33cffa1ce613

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NTVV9oamg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629141356915.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NTVV9oamg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NTVV9oamg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200629141431380.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NTVV9oamg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NTVV9oamg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200629141454253.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NTVV9oamg=,size_16,color_FFFFFF,t_70