- 本文中 \(n\) 代表著待排序序列的長度，
- 演算法是否穩定：多個相同的元素，若排序后這幾個元素的順序改變了就不穩定，反之穩定，
冒泡排序
又叫氣泡排序，起泡排序，泡沫排序
這應該是最簡單的排序演算法了吧，
在未排好序之前一直掃描序列，每次將最大數的放到序列的最后，所以最多 \(n-1\) 次掃描后序列就排好序了，
最差時間復雜度:\(O(n ^ 2)\)
最優時間復雜度:\(O(n)\)
平均時間復雜度:\(O(n ^ 2)\)
演算法是否穩定：是
這么慢我要它有什么用，
for(int i=1;i<n;++i) {//n-1輪掃描
bool okay=true;
for(int j=1;j<=n-i;++j) {//[n-i+2,n]都已經排好序了，
if(a[j]>a[j+1]) {
swap(a[j],a[j+1]);
okay=false;
}
}
if(okay==true) break;
}
上幾張動圖，幫助理解，
雞尾酒排序
冒泡排序的一種優化，又叫做雙向冒泡排序，雞尾酒攪拌排序，攪拌排序，漣漪排序，來回排序或快樂小時排序，你【龍門粗口】名字真多，
有兩種操作：
- 將序列中最大的數放到最后
- 將序列中最小的數放到最前
在未排好序之前將上面兩種操作交替進行，
最差時間復雜度:\(O(n ^ 2)\)
最優時間復雜度:\(O(n)\)
平均時間復雜度:\(O(n ^ 2)\)
演算法是否穩定：是
這么慢我要它有什么用，
好像沒看出來哪里優
以 \(\{2,3,4,5,1\}\) 為例,冒泡排序需要 \(4\) 次（指的是掃描整個序列的次數）：
\(\{2,3,4,5,1\} \rightarrow \{2,3,4,1,5\} \rightarrow \{2,3,1,4,5\} \rightarrow \{2,1,3,4,5\} \rightarrow \{1,2,3,4,5\}\)
而雞尾酒排序只需要 \(2\) 次（指的是掃描整個序列的次數）：
\(\{2,3,4,5,1\} \rightarrow \{2,3,4,1,5\} \rightarrow \{1,2,3,4,5\}\)
int left=1,right=n;//[left,right]需要排序，
while(left<right) {//最多進行到left=right就停止
bool okay=true;
for(int i=left;i<right;++i) {//將序列中最大的數放到最后
if(a[i]>a[i+1]) {
swap(a[i],a[i+1]);
okay=false;
}
}
if(okay==true) break;
--right;//[right+1,n]已經排好序了
for(int i=right;i>left;--i) {
if(a[i]<a[i-1]) {
swap(a[i],a[i-1]);
okay=false;
}
}
++left;//[1,left-1]已經排好序了
if(okay==true) break;
}
選擇排序
在未排好序之前一直掃描序列，每次將最小數的放到序列的最前，所以最多 \(n-1\) 次掃描后序列就排好序了，
與冒泡排序的不同：冒泡排序每掃一次序列會進行多次交換，將不符合順序的都交換，選擇排序每掃一次序列只會進行一次交換，將最小的元素與最前的元素交換，
最差時間復雜度\(O(n ^ 2)\)
最優時間復雜度\(O(n ^ 2)\)
平均時間復雜度\(O(n ^ 2)\)
演算法是否穩定：否
for(int i=1;i<n;++i) {//最多掃n-1次
bool okay=true;
int minn=0x7fffffff,flag;
for(int j=i;j<=n;++j) {
if(a[j]<minn) {
minn=a[j];flag=j;//找最小的并記錄下位置，
okay=false;
}
}
if(okay==true) break;
std::swap(a[i],a[flag]);//將最小的元素與最前的元素交換
}
放張圖理解一下
如{5,8,5,2,9}，可知選擇排序不穩定，
插入排序
流程就像是打牌的摸牌階段，
操作將一個數插入到一個排好序的序列中時期仍然排好序即可，在序列基本有序或者序列長度小時效率很高，
最差時間復雜度:\(O(n ^ 2)\)
最優時間復雜度:\(O(n)\)
平均時間復雜度:\(O(n ^ 2)\)
演算法是否穩定：是
for(int i=2;i<=n;++i) {//[1,i-1]已經排好了序
int temp=a[i],j=i-1;
while(j>0&&a[j]>temp) {//將第i張牌插入其中
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
上張動圖理解一下
二分插入排序
在插入排序的基礎上使用二分查找來確定當前數應該插入到哪里，
這是優化嗎？我為什么感覺比插入排序還慢，
時間復雜度:\(O(n(log n + n))\)
演算法是否穩定：是否
for(int i=2;i<=n;++i) {
int left=1,right=i-1,temp=a[i];
while(left<=right) {//二分查找當前數插入到哪里
int mid=(left+right)>>1;
if(a[mid]>temp) right=mid-1;
else left=mid+1;
}
for(int j=i-1;j>=left;--j) a[j+1]=a[j];
a[left]=temp;//插進去
}
對于if(a[mid]>temp) right=mid-1;
- 如果加了等號的話，不穩定排序
- 如果不加等號的話，是穩定排序
希爾排序
- 插入排序的特點：在序列基本有序或者序列長度小時效率很高，
運用了插入排序,現在我們有一個增量 \(x\) 一般為 \(\frac{n}{2}\) ,我們按照這個分量將整個序列分成 \(x\) 組，對每組進行插入排序（因為插入排序在需要排序的序列的長度很小的時候非常快），然后我們將增量減小一般為 \(x = \frac{x}{2}\) （最后增量一定會變成 \(1\) ，所以是必然正確的），重復上面的步驟，雖然增量在變小，序列長度在增加，但會變得越來越有序，也就越來越高效，
又叫縮小增量排序，
最差時間復雜度:\(O(n(logn) ^ 2)\)
最優時間復雜度:\(O(n)\)
演算法是否穩定：否
int ad=n/2;//增量一開始為n/2
while(ad>=1) {
for(int i=1;i<=ad;++i) {//分成ad組進行插入排序
for(int j=i+ad;j<=n;j+=ad) {//插入排序
int k=j-ad,temp=a[j];
while(k>=i&&a[k]>temp) {
a[k+ad]=a[k];k-=ad;
}
a[k+ad]=temp;
}
}
ad=ad/2;
}
之后可能會更新一下地精排序啥的，但之后再說，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/82031.html
標籤：C++