归并排序的实现

标签：归并 right 实现 mid int array 排序 left

基本思想

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

代码：

1.排序

2.分解左子树，分解右子树，找中间值

3.合并

以4个值为例

定义S1，mid,s2,right

定义一个临时数组，存入元素，

每次S1和S2进行比较，谁小谁入，并向后走，谁先走完，把没走完的存入临时数组中，最后for循环遍历临时数组，把他里面的元素存入原数组中，注意存入时，原数组要用i+left,因为不加右边的左值的话，就一直存入的是以0下标开始的值。

public static void mergeSort(int[] array){
        mergeSortFunc(array, 0,array.length-1);
    }
    //左右递归
    public static void mergeSortFunc(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
        mergeSortFunc(array,left,mid);//分解左边
        mergeSortFunc(array,mid+1,right);//分解右边
        merge(array,left,right,mid);//合并
    }
//合并
    private static void merge(int[] array, int left, int right, int mid) {
        int s1=left;
        int s2=mid+1;
        int[] tmpArr=new int[right-left+1];
        int k=0;//临时数组里的元素下标
        //证明两个区间都同时有数据
        while (s1 <= mid && s2 <= right) {
            if (array[s2] <= array[s1]) {
                tmpArr[k++] = array[s2++];
            } else {
                tmpArr[k++] = array[s1++];
            }
        }
        //若s1还有值
        while (s1<=mid){
            tmpArr[k++]=array[s1++];
        }
        //若s2还有值
        while (s2<=right){
            tmpArr[k++]=array[s2++];
        }
        //此时tmpArr里面一定是这个区间内有序数组了
        for (int i = 0; i < tmpArr.length; i++) {
            array[i+left]=tmpArr[i];//把右边的放进去
        }
    }

归并排序总结

1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度： O(N*logN) 3. 空间复杂度： O(N) 4. 稳定性：稳定

标签：归并,right,实现,mid,int,array,排序,left
From： https://blog.csdn.net/2401_86415114/article/details/143754700