归并排序

1.定义

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分**(divide)成一些小的问题然后递归求解，而治****(conquer)的阶段则将分的阶段得到的各答案“修补“在一起，即分而治之)**。

2.0个人理解

先把数组一直分 分成n组直到每组只有一个元素，然后在对每两组元素进行合并（因为他就是两组两组的分的就是用middle来分），合并时就先狗一个空数组，同时设置l1，l2为每一组元素的开头，再比较arr【l1】yuarr【l2】的大小，晓得就假如新数组，并++，最后再把这个数组的元素拷贝到原数组里。

3.图示讲解

eEfgzQ.md.png

4.0代码讲解

4.1不断分组的代码

终止条件同样也是l》=r，否则就是取中间值middle，再划分两组，最后进行合并

1
2
3
4
5
6
7
8
9
10
public static void  mergeSort(int left,int right,int[] arr){
        if (left>=right){
            return;
        }
        int mid=(left+right)/2;
        mergeSort(left,mid,arr);
        mergeSort(mid+1,right,arr);
        merge(left,right,mid,arr);

    }

4.2合并代码

找到两个数组收元素，i一个是left，j另一个是mid+1，新开一个数组copy，长度是right-left+1进行循环，当i<=mid,j<=right,比较arr【i】与arr【j】的大小，那个小，copy【k】就是那个，并且k++，小的那个下标j++，当有一个超过mid，那就一直是copy【k++】=arr【j+=】，若是超过right，那就是copy【k++】=arr【i++】，最后再把copy里的元素放回arr里

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
public static void merge(int left,int right,int mid,int[] arr){
        int i=left;
        int j=mid+1;
        int [] aux=new int[right-left+1];
        int t=0;
        while (i<=mid&&j<=right){
            if (arr[i]<arr[j]){
                aux[t]=arr[i];
                t++;
                i++;
            }else{
                aux[t]=arr[j];
                t++;
                j++;
            }
        }
        while (i<=mid){
            aux[t]=arr[i];
            t++;
            i++;
        }
        while (j<=right){
            aux[t]=arr[j];
            t++;
            j++;
        }
        int p=left;
        for (int k = 0; k < aux.length; k++) {
            arr[p+k]=aux[k];
        }
    }