java归并排序详解_java归并排序原理

---

一、归并排序原理

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

（图片来自比特就业课）

二、实例操作

现有如下两个有序数组array1和array2，让你合成一个有序数组array3
（这里以从小到大为例）

简言之就是让你从两个数组里取数字，有序的放到array3里面。

我们分别用s1,e1，s2,e2标记数组1和数组2的开头与末尾

比较s1下标和s2下标的值：1<2，s1下标值放入array3，s1++

比较s1下标和s2下标的值：6>2，s2下标值放入array3，s2++

比较s1下标和s2下标的值：6>3，s2下标值放入array3，s2++

比较s1下标和s2下标的值：6>4，s2下标值放入array3，s2++

比较s1下标和s2下标的值：6<9，s1下标值放入array3，s1++

比较s1下标和s2下标的值：7<9，s1下标值放入array3，s1++

比较s1下标和s2下标的值：10>9，s2下标值放入array3，s2++
这里我们发现，s2已经超过了e2，就说明，s2已经走完了，后面就不用比较s1下标和s2下标的值了，直接放array1里面的数就可以了。

s2>e2,直接放入array1里面的剩余数据
（简言之，一个数组走完了，后面直接放另一个数组的剩余数据即可）

三、实战代码

public static int[] mergeArray(int []arr1,int[]arr2){
        int s1=0;
        int s2=0;
        int e1=arr1.length-1;
        int e2=arr2.length-1;
        int []arr3=new int[arr1.length+arr2.length];//新数组长度是两数组长度和
        int bj1=0;//用于标记数组1是否是先遍历完的
        int bj2=0;//用于标记数组2是否是先遍历完的
        int i=0;//用于标记数组3下标
        while(s1<=e1&&s2<=e2){
            if(arr1[s1]<=arr2[s2]){
                arr3[i]=arr1[s1];
                s1++;
                if(s1>e1){//说明是数组1先遍历完的
                    bj1=1;
                }
            }else{
                arr3[i]=arr2[s2];
                s2++;
                if (s2>e2){//说明是数组2先遍历完的
                    bj2=1;
                }
            }
            i++;
        }
        if(bj1==1){//数组1先遍历完了，后面直接往数组3里面放数组2剩下元素即可
            while(s2<=e2){
                arr3[i++]=arr2[s2++];
            }
        }
        if(bj2==1){//数组2先遍历完了，后面直接往数组3里面放数组1剩下元素即可
            while(s1<=e1){
                arr3[i++]=arr1[s1++];
            }
        }
        return arr3;
    }
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

测试用例如下：

public static void main(String[] args) {
        int []arr1={1,6,7,10};
        int []arr2={2,3,4,9};
        int []arr3=mergeArray(arr1,arr2);
        System.out.println(Arrays.toString(arr3));
    }
1
2
3
4
5
6