> 文档中心 > 刷题百天计划 Day17 归并排序应用 小和问题 逆序对问题 中等

刷题百天计划 Day17 归并排序应用 小和问题 逆序对问题 中等

文章目录

  • 学习目标:
  • 学习内容:
  • 学习时间:
  • 学习产出:
    • 归并排序的应用

学习目标:

我会持续更新我独特的算法思路,希望能给大家带来不一样的思维拓展!
如果大家感觉有帮助的话,欢迎点赞关注支持哦!
你们的鼓励是我坚持下去的动力!
!!!

学习内容:

牛客网链接
在这里插入图片描述

学习时间:

2022.4.6

学习产出:

分析:
首先我们分析归并的两种情况
1.递归
2.利用R来作为Merge的长度

我们得到归并排序的时间复杂度为O(NlogN)就是这么推来的,首先R有1、2、4、8、16、32等情况,就是logN种,然后每一次R作为归并的长度的时候,arr执行的时间复杂度为O(N)。
所以logN种情况,每次O(N)
总时间复杂度为O(NlogN)
在这里插入图片描述
刷题百天计划 Day17 归并排序应用 小和问题 逆序对问题 中等

using System;class test{    static void Main(){ int count=Convert.ToInt32( Console.ReadLine()); string[] input=Console.ReadLine().Split(' ');  int[] arr=new int[count]; for(int i=0;i<count;i++){     arr[i]=Convert.ToInt32( input[i]); } Process(arr,0,count-1);  for(int i=0;i<count;i++){     Console.Write(arr[i]+" "); }    } static void Process(int[] arr,int L,int R){ if(L>=R){     return; } int Mid=L+((R-L)>>1); Process(arr,L,Mid); Process(arr,Mid+1,R); Merge(arr,L,Mid,R);    } static void Merge(int[] arr,int L,int Mid,int R){ int p1=L; int p2=Mid+1; int index=0; int[] help=new int[R-L+1]; while(p1<=Mid&&p2<=R){     help[index++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++]; } while(p1<=Mid){     help[index++]=arr[p1++]; } while(p2<=R){     help[index++]=arr[p2++]; }  for(int i=0;i<help.Length;i++){     arr[L+i]=help[i]; }    }}

归并排序的应用

1,小和问题
在这里插入图片描述

在这里插入图片描述
逆序对问题
刷题百天计划 Day17 归并排序应用 小和问题 逆序对问题 中等

在这里插入图片描述

全民K歌