七月挑戰一個月重刷完Y總算法基礎題，并且每道題寫詳細題解
進度:(3/106)?
歸并排序的思想也是分而治之
歸并優點：速度穩定,排序也穩定
排序也穩定（數組中有兩個一樣的值，排序之后他們的前后順序不發生變化，我們就說這個排序是穩定的）
缺點：比起快排，空間復雜度更高
使用場景：數據量巨大，尋求穩定
速度：穩定n(logn)
思想思路
第一步
找分界點（mid，中間值）
第二步
先遞歸排序兩邊
第三步
將兩個有序數組合二為一（歸并）
有序數組合并實現思路（歸并)
利用雙指針
準備三個數組和兩個指針
三個數組其中兩個是有序數組，一個是準備用來存儲的
#include<iostream>
#include<algorithm>
using namespace std;
int n,arr[10000010],sum[10000010];
void m_sort(int arr[],int l,int r){//到達邊界，退出if(l>=r)return;//找到分界點int mid=(l+r)>>1;//利用分界點分成兩個數組，遞歸兩個數組m_sort(arr,l,mid),m_sort(arr,mid+1,r);//上面遞歸結束的，一定是兩段有序數組//遍歷兩個數組，把兩個數組的值，按照歸并順序放到第三暫存個數組//這個兩個數組，其實指的是一個數組上的兩個有序區間//每次放入之前，先進行比較兩個數組里的指針指向的數//誰指向的數組元素小，先放誰進入第三個暫存數組//然后那個數組的指針指向下個元素,循環往復，直至其中一個數組遍歷完畢int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(arr[i]<arr[j])sum[k++]=arr[i++];else sum[k++]=arr[j++];}//上面的循環只保證其中一個數組遍歷完畢//下面的兩個循環，把未遍歷完畢的那個數組剩下的元素，添加進暫存數組while(i<=mid)sum[k++]=arr[i++];while(j<=r)sum[k++]=arr[j++];//把暫存數組，放入原數組，替代原數組元素，完成對arr[l-r]的排序for(int i=l,j=0;i<=r&&j<=k; i++,j++){arr[i]=sum[j]; }
}
int main(){cin>>n;for(int i=0;i<n;i++)cin>>arr[i];m_sort(arr,0,n-1);for(int i=0;i<n;i++)cout<<arr[i]<<' ';return 0;
}歸并排序已完成
感悟思想:歸并排序思想也是分而治之，但是和快排不同的是，快排是把大的放左邊，小的放右邊后
越遞歸，數組有序性越強，先分好再遞歸，歸并排序是先遞歸，再排序
先確定下標的中間，中位點的下標，也就是數組長度是十的話，中位點的下標就是5
然后直接就分別遞歸中位點的左邊和右邊
直到數組變成一位的時候，遞歸停止，開始回溯
回溯到數組是兩位的時候，現在的中位點左右兩邊，都是有序數組，只需要用兩個指針，各指向兩個數組
把小的，先放入新數組即可，后面同理，回溯時，中位點兩邊的數組一定都是有序數組
把兩個有序數組合并成新數組，只需要使用雙指針，把指向的數組的值較小的那個放入新數組，然后右移指針即可
直到回溯完畢，最后一次合并，原來的無序數組就排好了
有人叫回溯是回歸，回歸+合并，歸并排序。
經典題:逆序對的數量
題目
活動 - AcWing
思路
用分治的思想,mid將數組分成=兩段
則逆序對只有三種可能：
紅色，同時在左半邊，綠色，同時在右半邊，黃色，一半在左一半在右
我們先解決黃色情況
假設數組a[n]，數組b[n]都是兩個有序數組，且a[n]就是mid前0到mid的子串，b[n]是mid后mid+1到r的子串
使用雙指針算法，i，j分別指向數組第一個元素
a[i]和b[j]逐位比較
一旦b[j]小于a[i]中一個數，那說明，i到mid所有數，都和b[j]組成逆序對
因為a[]數組有序，a[i]到a[mid]的數必大于a[i]，也就必大于b[j]，也就必和b[j]組成逆序對
那我們只需要在兩者歸并排序時，累加記錄res+=mid-i+1;
res便是這兩個有序數組里的逆序對個數
（mid就是a[n]的長度，-i是減去已經指向過的數，+1是因為i從0開始）
黃色情況可以解決了，那只需要把所有情況都遞歸分割成黃色情況，所有情況都解決了
結論，只需要在歸并排序時，累加記錄arr[j]放在arr[i]前的情況時mid-(i+1)的值
代碼
這里只對改動部分注釋，看歸并排序點這歸并排序
#include<iostream>
using namespace std;
//數可能很大，使用long long
typedef long long ll;
int a[100010],s[100010];
ll add(int a[],int l,int r){if(l>=r)return 0;int mid=l+r>>1;//res接收值ll res=add(a,l,mid);//第二段的加上第一段的res+=add(a,mid+1,r);int k=0,i=l,j=mid+1;while(i<=mid&&j<=r){if(a[i]<=a[j])s[k++]=a[i++];else{//一旦a[j]需要放在a[i]前面//說明a[j]和a[i]以及a[i]到a[mid]所有數，都組成逆序對//mid-(i+1)的結果，就是a[i]到a[mid]的數的個數(+1是因為i從0開始)//每次出現這個時，把這個結果累加即可res+=mid-i+1;s[k++]=a[j++];}}while(i<=mid)s[k++]=a[i++];while(j<=r)s[k++]=a[j++];for(int i=0,j=l;j<=r;j++,i++){a[j]=s[i];}//處理完這段l-r,把res結果返回出去，處理下一段l-rreturn res;
}
int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}ll res=add(a,0,n-1);cout<<res<<endl;return 0;
}
)
