排序算法之归并排序_归并排序:用递归算法实现归并排序,在主函数中输入一些数据,并通过该递归函数进行

归并排序（Merge Sort）

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

归并排序的实现步骤：

1、实现一个合并方法，接受一个数组，开始位置，中间位置，结束位置
分成两个部分，两个部分依次进行元素比较，较小的元素添加至临时数组中。
2、左边元素多或右边元素多时，考虑将剩余得到元素添加至临时数组中。
3、将临时数组的元素覆盖接受的数组
3、递归实现排序，每次递归都分成两部分，直到不能再分时，调用合并方法

图片来自网络，侵删

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {2,3,5,1,4,6,8,10};
        /*merge(arr,0,2,arr.length-1);
        System.out.println(Arrays.toString(arr));//需要两边有序[1,3,5,2,4,6,8,10]-->[1, 2, 3, 4, 5, 6, 8, 10]
        */
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));//[1, 2, 3, 4, 5, 6, 8, 10]
    }
    //可以无序
    public static void mergeSort(int[] arr, int low, int high) {
        int mid = (low+high)/2;
        if(low<high)
        {//一直递归分为两部分，直到不能再分，进行比较，交换。
            mergeSort(arr,low,mid);//左部递归递归变成两两比较交换变有序
            mergeSort(arr,mid+1,high);//右部递归递归变成两两比较交换变有序
            merge(arr,low,mid,high);//有序的左大半部和有序的右大半部进行合并
        }
    }
    //需要有序
    public static void merge(int[] arr,int low,int middle,int high)
    {
        //临时数组的长度，不能是arr.length因为不确定low和high全部包括数组
        int[] temp = new int[high-low+1];
        //定义左指针
        int i = low;
        //定义右指针
        int j = middle+1;
        //临时数组的索引
        int index =0;
        //循环将左边和右边的元素依次比较放入临时数组中
        while(i<=middle&&j<=high)
        {
            if(arr[i]<arr[j])
            {
                temp[index++]=arr[i++];
            }
            else
            {
                temp[index++]=arr[j++];
            }
        }
        //如果左边的元素多，考虑将左边的元素在添加至临时数组
        while(i<=middle)
        {
            temp[index++]=arr[i++];
        }
        //同样，右边的元素
        while(j<=high)
        {
            temp[index++]=arr[j++];
        }
        //将临时数组元素覆盖接受的数组
        for (int k = 0; k < temp.length; k++) {
            arr[k+low]=temp[k];
        }
    }
}
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