欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基本算法——并归排序

程序员文章站 2023-12-27 08:07:45
...

掌握并归排序

  • AcWing787 并归排序
  • AcWing788 逆序对的数量

并归排序

并归排序的核心思想是分治

  • 分界点
  • 递归左右
  • 并归

分到不可再分后、合起来就是排序好的了

基本算法——并归排序

基本算法——并归排序

// 输入和快排的一样
public static void mergeSort(int[] arr, int l, int r){
    //递归结束条件
    if(l >= r) return;
    //1. 获得分界点,注意一定是mid,是索引,而不是值
    int mid = l + r >> 1; 
    
    //2. 递归过程
    mergeSort(arr, l, mid);
    mergeSort(arr, mid+1, r);
    
    //3. 归并过程
    int[] tmp = new int[r-l+1]; //零时数组
    int i = l; 
    int j = mid+1;
    int k = 0;
	
    //每次都将小的过去
    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];
    } 
}

并归排序的应用-逆序对的数量

什么是逆序对?
基本算法——并归排序
那么如何利用并归快速求解逆序对问题呢?

  1. 首先并归有个步骤是拆成两半,假设我们的并归算法可以返回逆序对
    • 在归并中
    • 左半边的逆序对 mergeSort(l, mid)
    • 右半边的逆序对 mergeSort(mid+1, r)
    • 左右情况的逆序对 (最关键)? 归并结束后,有序了
    • 然后呢?mid-i+1

基本算法——并归排序

基本算法——并归排序

相关标签: 算法学习 算法

上一篇:

下一篇: