基础算法篇——归并排序

时间：2022-11-02 10:09:44

本次我们介绍基础算法中的快速排序，我们会从下面几个角度来介绍快速排序：

  • 归并排序思想
  • 归并排序代码
  • 归并排序拓展

归并排序思想

我们首先来介绍归并排序思想（分治思想）：

  1. 确定分界点
我们首先确定整个数组的分界点
以我们的习惯而言还是以arr[l],arr[r],arr[(r+l)/2]为分界点
  1. 递归排序
我们首先需要将数组分界点两侧进行分组，这时他们会划分为左侧和右侧
我们再对已经划分的左侧和右侧进行分界点分组，这时就会划分为4个分组
依次类推，直到每个分组数为1时结束分组，然后我们才会开始进行归并操作
  1. 归并数组
这个方法需要额外空间：我们需要一个新数组来装排序完成的数组
我们首先对最后一次分组的左右侧进行归并，将两组个数为1的分组化为一个排序整齐的组
依次类推，我们从开始的一个数为一组变为两个数为一组，逐渐归并，直到最后所有数都变为一组

至于归并的方法：
我们目前左右两侧的数组是顺序排列，我们只需要依次比较左右两侧最小数的大小
我们依旧采用指针的方法，左侧指向l，右侧指向mid+1，同时比较两者大小，将较小的数拿出来放在数组中，并且将指针向后移动一位

归并排序代码

我们这里给出归并排序的代码展示：

import java.util.Scanner;

public class Main {

    public static final int N = 10000010;

    // 额外空间数组：这里也可以在归并方法中设置，设置大小为r-l+1即可满足条件
    public static int[] tmp = new int[N];

    public static void main(String[] args) {

        // 给出数组

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

        // 打印数组
        System.out.print("排序前：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println(" ");

        // 进行归并排序
        merge_sort(arr,0,n-1);

        // 打印数组
        System.out.print("排序后：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println(" ");

    }

    private static void merge_sort(int[] arr,int l,int r) {

        // 判断还存在数组？
        if (l >= r) return;

        // 设置中间值
        int mid = (l+r)/2;

        // 先进行排序
        merge_sort(arr,l,mid);
        merge_sort(arr,mid+1,r);

        // 对左右两侧进行判断

        // k是目前排序的数,i,j为左右两侧指针
        int k = 0;
        int i = l,j = mid + 1;

        // 比较判断
        while (i <= mid && j <= r){
            if (arr[i] < arr[j]){
                tmp[k++] = arr[i++];
            }else {
                tmp[k++] = arr[j++];
            }
        }

        // 判断左右剩余？然后累加在最后
        while (i <= mid){
            tmp[k++] = arr[i++];
        }
        while (j <= r){
            tmp[k++] = arr[j++];
        }

        // 最后赋值回去
        for (i = l, j = 0; i <= r;i++,j++){
            arr[i] = tmp[j];
        }
    }
}

归并排序拓展

题目：

  • 给定一个长度为n的整数数列，请你计算数列中的逆序对的数量

逆序对定义：

  • 对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

解题思路：

  • 我们采用分治的思想，使用归并排序将逆序对的数量统计分为三部分
  • 第一部分：左半边逆序对数量meger_sort(L,mid)
  • 第二部分：右半边逆序对数量meger_sort(mid+1,R)
  • 第三部分：左右两侧逆序对数量

解题要点：

  • 实际上我们的第一部分和第二部分的数量计算都是基于第三部分的逆序对统计，所以我们只需要思考第三部分的计算

解题方法：

  • 我们左右两侧的数都是按照顺序排列
  • 所以我们只需要按顺序将大于右侧某个数的左侧的第一个数找出来，然后该数后面的数都会大于右侧的数
  • 我们通过简单的计算可以得知，该数所对应的逆序对的个数为mid - i + 1

解题代码：

import java.util.Scanner;

public class mmm {

    private static final int N = 1000010;

    private static int[] tmp = new int[N];

    // 逆序对个数
    private static int result = 0;

    public static void main(String[] args) {
        
        // 基本归并框架

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int[] arr = new int[n];

        for (int i = 0;i < arr.length;i++){
            arr[i] = scanner.nextInt();
        }

        System.out.print("排序前：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println("");

        merge_sort(arr,0,n-1);


        System.out.print("排序后：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println("");

        System.out.println("逆序对共" + result + "个");
    }

    private static void merge_sort(int[] arr,int l,int r) {

        if (l >= r) return;

        int mid = (l+r)/2;

        merge_sort(arr, l, mid);
        merge_sort(arr,mid+1,r);

        int k = 0;
        int i = l,j = mid+1;

        while (i <= mid && j<= r){
            if (arr[i] < arr[j]){
                tmp[k++] = arr[i++];
            }else {
                tmp[k++] = arr[j++];
                // 我们找到了右侧该数的针对左侧最小的大于该数的值，并根据其计算逆序对
                result += mid - i + 1;
            }
        }

        while (i <= mid){
            tmp[k++] = arr[i++];
        }
        while (j <= r){
            tmp[k++] = arr[j++];
        }

        for (i=l,j=0;i<=r;i++,j++){
            arr[i] = tmp[j];
        }
    }
}

结束语

好的，关于基础算法篇的归并排序就介绍到这里，希望能为你带来帮助~

相关文章