归并排序

# 归并排序

# 归并排序思想

归并排序采用分治策略(将问题分成一些小问题后递归求解)，先说分:将一个数组按照等分机制等分下去直到数组不能再等分。在说治: 治也就是归并到这一步就要将上步分的结果一步步归并而在归并的过程中进行排序。

# 归并排序推理

现给定一个数组 int[] arr={8,4,5,7,1,3,6,2}

# 推理图

# 分治图

每次可以按照数组长度/2进行等分，直到元素不能再被等分

# 归并图

根据上图可知归并我们需要left指针和一个right指针。而对于right指针就是分界值加1(nums.length/2+1)
将left指针索引处的值和right指针索引处的值相互比较。谁小的话就放到临时数组中。同时小的那边指针向右移
以此类推直到任何一边指针无法在移动。将有剩余元素的一边依次放入到临时数组。

1
2
3

# 分解图

1. 0 ~ 7分为0 ~ 3和4 ~ 7两组
2. 0 ~ 3分为0 ~ 1和2 ~ 3两组
3. 0 ~ 1分为 0和1
然后0和1整理为有序数组

4. 2 ~ 3分为 2 和 3
然后2 和3 进行整理为有序数组
再将 0 ~ 1和2 ~ 3进行整理为有序数组

5. 4 ~ 7分为 4 ~ 5和 6 ~ 7两组
以此类推
最后整理成为有序数组

1
2
3
4
5
6
7
8
9
10
11
12

# 代码实现


 public static void main(String[] args) {
        int num []={8,4,5,7,1,3,6,2};
        sort(num,0,num.length-1,new int[num.length]);
        System.out.println(Arrays.toString(num));
    }

    /**
     * 数组分解
     * @param nums 原数组
     * @param left 左指针
     * @param right 右指针
     * @param numnew[] 临时数组
     */
    public static void sort(int nums[],int left,int right,int numnew[]){
            //当left>=right就代表无法在进行等分。
            if(left>=right) {
                return;
            }
            //下次要拆分的中间值
            int midNew = (left + right) / 2;
            //左子组分解
            sort(nums, left, midNew, numnew);
            //右子组分解
            sort(nums, midNew + 1, right, numnew);
            //归并
            merge(nums, left, right, midNew, numnew);
    }


    /**
     * 归并
     * @param nums 原数组
     * @param left 左指针
     * @param right 右指针
     * @param mid  分界值
     * @param temp 临时数组
     */
    public static void merge(int nums[],int left,int right,int mid,int temp[]){

        //右子组第一个值
        int j=mid+1;
        //左子组第一个值
        int h=left;
        //记录temp数组下标
        int index=left;

        //当左子组 或者 右子组任何一个移动到最后了 停止循环
        while (h<=mid && j<=right){
            //左子组和右子组比较 哪个小就入临时数组
            if(nums[h]<=nums[j]){
                temp[index]=nums[h];
                h++; //左子组移动指针到下一个
                index++;
            }else{
                temp[index]=nums[j];
                j++; //右子组移动指针到下一个
                index++;
            }
        }

        // 根据前面所讲的，左子组和右子组其中一个肯定有一个是有剩余元素的。依次入temp数组。

        // 当左子组还有剩余的，依次入临时数组
        while (h<=mid){
            temp[index]=nums[h];
            h++;
            index++;
        }
        // 当右子组还有剩余的，依次入临时数组
        while (j<=right){
            temp[index]=nums[j];
            j++;
            index++;
        }

        //for循环 将临时表copy到原数组。
        for (int i=left;i<=right;i++){
            nums[i]=temp[i];
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

# 时间复杂度

那对于时间复杂度就是:O(nlogn)

# 空间复杂度

空间复杂度就是:O(n)

# 稳定性

归并排序属于稳定的排序

编辑

上次更新: 2022/08/02, 09:18:22

← 快速排序