Java实现归并排序

java实现归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并操作的工作原理如下：

第一步： 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步： 设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步： 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

时间复杂度：O(n log n)

代码实现：

//归并排序  从小到大
public class MergetSort {
    public static void main(String[] args) {

        int[] arr={8,4,5,7,1,3,6,2};
        int[] temp= new int[arr.length];
        mergetSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(temp));
    }

    /**
     * 块分开+合一   的方法
     * @param arr 需要排序的数组
     * @param left 数组左边的索引
     * @param right 数组右边的索引
     * @param temp 做中转的数组
     */
    public static void mergetSort(int[] arr,int left,int right,int[] temp){
        if (left<right){
            int mid=(left+right)/2;//中间的索引
            //向左递归  进行分解
            mergetSort(arr,left,mid,temp);
            //向右递归  进行分解
            mergetSort(arr,mid+1,right,temp);
            //将分开的数  进行合并
            merget(arr,left,mid,right,temp);
        }

    }



    /**
     * 先写一个合并的方法
     *
     * @param arr   需要排序的数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间序列的索引
     * @param right 右边序列的索引
     * @param temp  做中转的数组
     */
    public static void merget(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;  //初始化i，左边有序序列的初始索引
        int j = mid + 1;  //初始化j，右边有序序列的初始索引
        int l = 0;  //指向temp数组的当前索引

        //先把左右两边  有序的  按照规则填充到temp数组中
        //直到 有一边的数组已经处理完毕
        while (i <= mid && j <= right) {
            //如果左边有序序列的当前元素 小于右边的有序序列的当前元素
            //即将左边的当前元素，填充到team
            //让后 l++   i++
            if (arr[i] < arr[j]) {
                temp[l] = arr[i];
                l += 1;
                i += 1;
            } else {  //反之 将右边的当前元素  填充到team数组中
                temp[l] = arr[j];
                l += 1;
                j += 1;
            }
        }

        //把剩余数组 依次填充到teamp 数组中

        //如果左边的有序序列还有剩余的元素，就全部填充到team中
        while (i <= mid) {
            temp[l] = arr[i];
            l += 1;
            i += 1;
        }

        //如果右边的有序序列有剩余的元素，也全部填充到team中
        while (j <= right) {
            temp[l] = arr[j];
            l += 1;
            j += 1;
        }

        //将team中 有序的元素，添加到 arr数组中
        l=0;
        int tempLeft = left; //
        //第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
        //最后一次 tempLeft = 0  right = 7
        while(tempLeft <= right) {
            arr[tempLeft] = temp[l];
            l += 1;
            tempLeft += 1;
        }
        
    }

}