歸并排序

歸并排序（merge sort）是高效的基于比較的穩定排序算法。

1.歸并排序的復雜度分析

歸并排序的時間復雜度為$O(nlogn)$

歸并排序的空間復雜度是 $O(n)$（這是因為他不是原地排序算法）

2.細節解釋

$(l+r)>>1=(l+r)÷2^1=(l+r)÷2$;

3.歸并排序動圖演示

在這里我們是默認了它以中間為節點，分別排成了從大到小的兩個序列的

這是因為有merge_sort(q,l,mid),merge_sort(q,mid+1,r)來不斷進行拆分的原因

3(1) 我們的拆分過程如下↓

這里的動圖演示，先執行了下方代碼

	int k=0,i=l,j=mid+1;//i表示左半邊的開始，j表示右半邊的開始，k表示合并的個數while(i<=mid&&j<=r){//對半分后,mid是i的終點,r是j的終點if(q[i]<=q[j])  tmp[k++]=q[i++];//不斷將tmp填充，i++else tmp[k++]=q[j++];//else 等同于if(q[i]>q[j]) }

當q[i]和q[j]已經超過了他們的終點（i的終點是mid，j的終點是r），那么就執行下方代碼

	while(i<=mid) tmp[k++]=q[i++];//將i沒有填充完的繼續進行填充while(j<=r) tmp[k++]=q[j++];//將j沒有填充完的繼續進行填充

執行上方代碼時一定有一個值(i or j) 是已經超過了他們的終點的，不然不會退出循環，所以不用考慮大小關系

執行上方代碼是為了將剩下的可以填充的數給填充進tmp數組里，以此來保證沒有遺漏

動圖演示↓

4.code↓

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,a[maxn] ,tmp[maxn];
void merge_sort(int q[],int l,int r){//要排序的數組，左邊界，有邊界if(l>=r) return;//不滿足要求int mid=(l+r)>>1;//m是l+r的中間值,(l+r)>>1=(l+r)/(2^{1})=(l+r)/2;merge_sort(q,l,mid),merge_sort(q,mid+1,r);//不斷將它進行拆分，然后歸并int k=0,i=l,j=mid+1;//i表示左半邊的開始，j表示右半邊的開始，k表示合并的個數while(i<=mid&&j<=r){//對半分后,mid是i的終點,r是j的終點if(q[i]<=q[j])  tmp[k++]=q[i++];//不斷將tmp填充，i++else tmp[k++]=q[j++];//else 等同于if(q[i]>q[j]) }while(i<=mid) tmp[k++]=q[i++];//將i沒有填充完的繼續進行填充while(j<=r) tmp[k++]=q[j++];//將j沒有填充完的繼續進行填充for(int i=l,j=0;i<=r;i++,j++){q[i]=tmp[j];//將已經排好序的(tmp[l]~tmp[r])給賦值到q數組}
}
int main(){ios::sync_with_stdio(false);//加速cincin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<n;i++){cin>>a[i];//輸入數列}merge_sort(a,0,n-1);//進行排序for(int i=0;i<n;i++){cout<<a[i]<<" ";//進行排好序了的進行輸出}return 0;
}

洛谷P1177【模板】排序

題意：將讀入的 $N$個數從小到大排序后輸出

數據規模與約定

對于 $20\%$ 的數據，有 $1\le N\le 10^3$；

對于 $100\%$ 的數據，有 $1\le N\le 10^5$，$1\le a_i\le 10^9$。

code（歸并排序）↓

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,a[maxn] ,tmp[maxn];
void merge_sort(int q[],int l,int r){if(l>=r) return;int mid=(l+r)>>1;merge_sort(q,l,mid),merge_sort(q,mid+1,r);int k=0,i=l,j=mid+1;while(i<=mid&&j<=r){if(q[i]<=q[j])  tmp[k++]=q[i++];else tmp[k++]=q[j++];}while(i<=mid) tmp[k++]=q[i++];while(j<=r) tmp[k++]=q[j++];for(int i=l,j=0;i<=r;i++,j++){q[i]=tmp[j];}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<n;i++){cin>>a[i];}merge_sort(a,0,n-1);for(int i=0;i<n;i++){cout<<a[i]<<" ";}return 0;
}

code（sort排序【快速排序】）

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,a[maxn]={};
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a,a+1+n);for(int i=1;i<=n;i++) cout<<a[i]<<" ";return 0;
}

完結撒花(￣▽￣) /