Loading...
墨滴

代码界的小白

2021/11/04  阅读:46  主题:前端之巅同款

8大常见排序算法之归并排序

归并排序

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

原理

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

第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置

第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾

Java代码

//递归方法
package MergeSort;
public class MergeSort {   
    public static int[] mergeSort(int[] nums, int l, int h) {
        if (l == h) //左右相遇的时候
            return new int[] { nums[l] };
         
        int mid = l + (h - l) / 2;
        int[] leftArr = mergeSort(nums, l, mid); //左有序数组
        int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
        int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
         
        int m = 0, i = 0, j = 0
        //分别比较左数组与右数组的大学
        while (i < leftArr.length && j < rightArr.length) {
            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        //如果左数组还有空余
        while (i < leftArr.length)
            newNum[m++] = leftArr[i++];
        //如果右数组有空余
        while (j < rightArr.length)
            newNum[m++] = rightArr[j++];
        return newNum;
    }
    public static void main(String[] args) {
        int[] nums = new int[] { 9876543210 };
        int[] newNums = mergeSort(nums, 0, nums.length - 1);
        for (int x : newNums) {
            System.out.println(x);
        }
    }
}

时间复杂度

归并排序比较占用内存,但却是一种效率高且稳定的算法。

改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值,则说明序列可以直接形成一段有序序列不需要再归并,反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)

TimSort可以说是归并排序的终极优化版本,主要思想就是检测序列中的天然有序子段(若检测到严格降序子段则翻转序列为升序子段)。在最好情况下无论升序还是降序都可以使时间复杂度降至为O(n),具有很强的自适应性。

空间复杂度

由前面的算法说明可知,算法处理过程中,需要一个大小为n的临时存储空间用以保存合并序列。

算法稳定

在归并排序中,相等的元素的顺序不会改变,所以它是稳定的算法。

使用场景

题目描述:

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

如果两个区间为[4, 3] 和[1, 2] 那么逆序数为(4,1),(4,2),(3,1),(3,2),同样的如果区间变为有序,比如[3,4] 和 [1,2]的结果是一样的,也就是说区间有序和无序结果是一样的。

但是如果区间有序会有什么好处吗?当然,如果区间有序,比如[3,4] 和 [1,2] 如果3 > 1, 显然3后面的所有数都是大于1, 这里为 4 > 1, 明白其中的奥秘了吧。所以我们可以在合并的时候利用这个规则。

代码

public class Solution {
    int result = 0;
    int[] temp;
    public int InversePairs(int [] array) {
        temp = new int[array.length];
        Mergsort(array,0,array.length-1);
        return result;
    }
    public  void Mergsort(int []array,int first,int last){
        if(first>=last) return;
        int mid = first +((last-first)/2);
        Mergsort(array,first,mid);
        Mergsort(array,mid+1,last);
        Mergsort_l(array,first,mid,last);
    }
    public  void Mergsort_l(int []array,int first,int mid,int last){
        int i =first,j = mid+1,k=0;
        while(i<=mid&&j<=last){
            if(array[i]>=array[j]){//这块与归并排序有些区别,归并排序时array[i]<array[j] 
                temp[k++] = array[j++];
                result += (mid-i+1);//奥妙之处
                result %= 1000000007;
            }else{
                temp[k++] = array[i++];
            }
        }
        while(i<=mid){
            temp[k++] = array[i++];
        }
        while(j<=last){
            temp[k++] = array[j++];
        }
        for( k = 0,i = first;i<=last;++i,++k){
            array[i] = temp[k];
        }
    }
}

推荐阅读

代码界的小白

2021/11/04  阅读:46  主题:前端之巅同款

作者介绍

代码界的小白

公众号:代码界的小白