归并排序原理及代码实现

桃扇骨 2023-09-27 12:49 117阅读 0赞

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

**排序原理：**

1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1 为止；

2.将相邻的两个子组进行合并成一个有序的大组；

3.不断的重复步骤 2 ，直到最终只有一个组为止。

图解：

![a09058b82a544f0f93b7cdd4c0237a31.png][]

每次比较时，将两组p指针处的数据进行比较，小的放入辅助数组中，当其中一组比较完成后，另外一组则以此放入辅助数组，即完成排序。

![85a7316a3f1148a294b0f739d3c51848.png][] ![547e3fb1eff5471f841225fb18fb5c14.png][]

代码实现：

1.分解法：将每个步骤细分成一个方法，方法之间调用完成归并排序；

import java.util.Arrays;
    
    /**
     * 归并排序
     */
    public class Merge {
    
        public static void main(String[] args) {
            int aa[] = {3,4,6,3,2,6,8,9,3};
            sort(aa);
            System.out.println(Arrays.toString(aa));
        }
    
        //完成归并操作需要的辅助数组
        private static int[] assist;
    
        /**
         * 总排序方法
         * @param arr 待排序数组
         */
        public static void sort(int[] arr) {
            assist = new int[arr.length];//创建辅助数组
            int lo = 0;
            int hi = arr.length - 1;
            //调用 sort 方法对数组索引 lo 到索引 hi 之间的元素进行排序
            sort(arr, lo, hi);
        }
    
        /**
         * 对数组 arr 中从索引 lo 到索引 hi 之间的元素进行排序
         * @param arr
         * @param lo
         * @param hi
         */
        private static void sort(int[] arr, int lo, int hi) {
            if(hi <= lo) {
                return;
            }
    
            //定义中间索引分组
            int mid = lo + (hi - lo) / 2;
            //分组排序
            sort(arr, lo, mid);
            sort(arr, mid + 1, hi);
            //对 lo 到 mid 和 mid+1 到 hi 两组数据归并排序
            merge(arr, lo, mid, hi);
        }
    
        /**
         * 从索引 lo 索引 mid 为一个子组，从索引 mid+1 到索引 hi 为另一个子组，
         * 把数组 arr 中的这两个子组的数据合并成一个有序的大组（从索引 lo 到索引 hi）
         * @param arr
         * @param lo
         * @param mid
         * @param hi
         */
        private static void merge(int[] arr, int lo, int mid, int hi) {
            //定义三个指针
            int i = lo;//指向辅助数组中开始填充数据的索引
            int p1 = lo;//指向前半组的第一个数据索引
            int p2 = mid + 1;//指向后半组第一个数据索引
    
            //开始比较左右两组数据大小，将小的填充到辅助数组中
            while (p1 <= mid && p2 <= hi) {//当有一个指针移动到该组数的边界后，则该组遍历结束，结束循环
                //判断两组数大小，小的放入辅助数组
                if (arr[p1] < arr[p2]) {
                    assist[i] = arr[p1];//放入小的在辅助数组中
                    i++; //辅助数组指针向后移动一位
                    p1++;//p1指针向后移动一位
                } else {
                    assist[i] = arr[p2];
                    i++;
                    p2++;//p2指针向后移动一位
                }
            }
    
            //上面while循环结束后，会出现一组数据已全部遍历结束并放入辅助数组中，
            //只需将未遍历完的另一组数据依次填充到辅助数组中即可
            while (p1 <= mid) {//第一组数据未遍历完
                assist[i++] = arr[p1++];
            }
            while (p2 <= hi) {//第二组数据未遍历完
                assist[i++] = arr[p2++];
            }
    
            //所有数据均已遍历完
            //将辅助数组复制到初始数组中
            for (int j = lo; j <= hi; j++) {
                arr[j] = assist[j];
            }
    
        }
    }

2.直接法：一个方法内完成

public static int[] mergeSort(int[] nums, int lo, int hi) {
            if (lo == hi) {
                return new int[]{nums[lo]};
            }
            int mid = lo + (hi - lo) / 2;
            int[] leftArr = mergeSort(nums, lo, mid); //左有序数组
            int[] rightArr = mergeSort(nums, mid + 1, hi); //右有序数组
            int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组，用来存放排序好的数据
    
            int i = 0, p1 = 0, p2 = 0;
            while (p1 < leftArr.length && p2 < rightArr.length) {
                newNum[i++] = leftArr[p1] <= rightArr[p2] ? leftArr[p1++] : rightArr[p2++];
            }
            while (p1 < leftArr.length)
                newNum[i++] = leftArr[p1++];
            while (p2 < rightArr.length)
                newNum[i++] = rightArr[p2++];
            return newNum;
        }
    
        @Test
        public void test1() {
            int[] nums = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 10};
            int[] newNums = mergeSort(nums, 0, nums.length - 1);
            System.out.println(Arrays.toString(newNums));
        }

**归并排序的优缺点：**

归并排序的时间复杂度为O(nlogn)，需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的操作。

归并排序在归并的过程中，只有arr\[i\]<arr\[i+1\]的时候才会交换位置，如果两个元素相等则不会交换位置，所以它并不会破坏稳定性，归并排序是稳定的。

[a09058b82a544f0f93b7cdd4c0237a31.png]: https://img-blog.csdnimg.cn/a09058b82a544f0f93b7cdd4c0237a31.png
[85a7316a3f1148a294b0f739d3c51848.png]: https://img-blog.csdnimg.cn/85a7316a3f1148a294b0f739d3c51848.png
[547e3fb1eff5471f841225fb18fb5c14.png]: https://img-blog.csdnimg.cn/547e3fb1eff5471f841225fb18fb5c14.png