- 本文中 \(n\) 代表著待排序序列的長度，
- 演算法是否穩定：若 \(a_i = a_j \ , \ i < j\)，排序后若\(i < j\) 則穩定，反之不穩定，（可能有點歧義炊訓看）
歸并排序
用了二分的思想，
在遞回的程序中不斷將需要排序的區間縮小，使小區間有序后，再使大區間變得有序會簡單很多，
最差時間復雜度:\(O(nlogn)\)
最優時間復雜度:\(O(nlogn)\)
平均時間復雜度:\(O(nlogn)\)
演算法是否穩定：是
void mergesort(int l,int r,int mid) {//將[l,r]區間排好序
int i=l,j=mid+1,cnt=0;//[l,mid]與[mid+1,r]已經有序了，所以可以進行下面的操作，
while(i<=mid&&j<=r) temp[++cnt]=a[i]<=a[j]?a[i++]:a[j++];
while(i<=mid) temp[++cnt]=a[i++];
while(j<=r) temp[++cnt]=a[j++];
for(int i=l;i<=r;++i) a[i]=temp[i-l+1];
}
void merge(int l,int r) {//不斷將區間縮小
if(l==r) return;
int mid=(l+r)>>1;
merge(l,mid),merge(mid+1,r);
mergesort(l,r,mid);return;//遞回，先給小區間排序后大區間，
}
merge(1,n);
上張圖理解一下：
可用于求逆序對的個數，
堆排序
不想寫，咕咕咕，
快速排序
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/82043.html
標籤：C++
上一篇：Qt事件分發機制原始碼分析之QApplication物件構建程序
下一篇：C++ 進階筆記之一