本文將用說人話+動圖的形式帶你搞懂常見排序演算法，簡要分析復雜度、穩定性等指標，并給出參考代碼，最后安利sort()函式的使用，

選擇排序

每次選擇后面最小的元素放在前面，

• 時間復雜度 O ( n 2 ) O(n^2) O(n2)
• 穩定性：不穩定
  如2 2 1，第一趟選出最小的1后交換得到1 2 2，兩個2相對位置改變，

穩定性：就是（關鍵字/元素值）相同的元素排序后的相對位置是否改變，

• 排序趟數是否與原序列有關：無關
  無論升序亂序，選擇排序每趟都要遍歷到最后一個元素，才能確保選出的元素是最小的，

#include<bits/stdc++.h>
using namespace std;
void selection(int a[],int n){
	for(int i=0;i<n;i++){
		int min=i;  //記錄最小元素
		for(int j=i+1;j<n;j++){  //找出后面最小元素
			if(a[j]<a[min])
				min=j;
		}
		swap(a[i],a[min]);  //交換
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	selection(a,5);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

冒泡排序

從前往后比較兩兩相鄰的元素，如果前者>后者，則交換它們，元素就像氣泡一樣往后冒，

• 時間復雜度 O ( n 2 ) O(n^2) O(n2)

• 穩定性：穩定
  遇到相同或更大元素時，不會交換，

• 排序趟數是否與原序列有關：有關
  已經升序的極端條件下，可以記錄是否發生交換，若無交換則序列有序，退出即可，

#include<bits/stdc++.h>
using namespace std;
void bubble(int a[],int n){
	for(int i=0;i<n;i++){
		bool tag=false;  //記錄此趟是否發生交換
		for(int j=0;j<n-i-1;j++){//后面i個最大的已冒到頂了不用管(寫成n問題也不大)
			if(a[j]>a[j+1]){  //和后一個元素比較
				swap(a[j],a[j+1]);
				tag=true;
			}
		}
		if(tag==false)break;  //沒有發生交換，退出
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	bubble(a,5);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

插入排序

每次將待排序的元素正確插入到前面已經排好序的序列中，就像理撲克牌一樣，

• 時間復雜度 O ( n 2 ) O(n^2) O(n2)

• 穩定性：穩定
  從后向前先比較再移動，遇到相同不會交換，

• 排序趟數是否與原序列有關：無關
  每趟插入1個元素，固定n-1趟，

#include<bits/stdc++.h>
using namespace std;
void insertion(int a[],int n){
	for(int i=0;i<n;i++){  //遍歷i個待插元素
		for(int j=i;j>0;j--){  //插入前面
			if(a[j]<a[j-1])  //小則交換 
				swap(a[j],a[j-1]);
			else break;  //否則已插入正確位置
			//其實不break問題也不大，都是n方 
		}
	}
}
int main(){
	int a[5]={1,2,3,4,5};
	insertion(a,5);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

希爾排序

每次把相隔x（增量）的元素劃分成一個子表，進行直接插入排序（先不管其他元素），然后不斷縮小x，從基本有序到整體有序，

• 時間復雜度 O ( n 2 ) O(n^2) O(n2)
• 穩定性：不穩定
  相同元素被劃分到不同子表時，可能會改變它們的相對位置，
• 排序趟數是否與原序列有關：無關
  無論原序列狀態如何，都只與增量x（即陣列大小n）有關，

#include<bits/stdc++.h>
using namespace std;
void shell(int a[],int n){
	for(int x=n/2;x>0;x/=2){  //增量x 
		for(int i=x;i<n;i++){  //劃分子表 
			//子表內插入排序 
			for(int j=i;j>=x&&a[j]<a[j-x];j-=x) 
				swap(a[j],a[j-x]);
		}
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	shell(a,5);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

快速排序

每趟將比該元素大的放在它右邊，比它小的放在它左邊，那么該元素的位置就確定了，再遞回的排序其他元素即可，

• 時間復雜度 O ( n l o g n ) O(nlogn) O(nlogn)
  需要確定 n n n個數的正確位置，每趟最多比較次左右兩半區間，復雜度是 O ( l o g n ) O(logn) O(logn)，

• 穩定性：不穩定
  在交換左右兩邊的數時會改變相對位置，

• 排序趟數是否與原序列有關：有關
  根據所選的數，來移動兩邊的數，使左小右大，在逆序的極端條件下，復雜度退化成 O ( n 2 ) O(n^2) O(n2)（每趟都要把右邊的數全部移到左邊），
  優化tip：選數不要默認選第一個數(cur=a[low])，可以隨機，亦可以選頭中尾三個數的中位數，使左右兩半大小盡可能相等，從而減少移動次數，

快排YYDS，不少演算法題也涉及快排思想，

#include<bits/stdc++.h>
using namespace std;
int partition(int a[],int low,int high){  //一趟劃分
	int cur=a[low];  //選第一個數來劃分  
	while(low<high){
		while(low<high&&a[high]>=cur)high--;  //從后往前找比當前值小的元素
		a[low]=a[high];  //把小的換到前面去
		while(low<high&&a[low]<=cur)low++;  //從前往后找比當前值大的元素
		a[high]=a[low];  //把大的換到后面去
	}
	//當low=high，跳出回圈，這個位置就是當前元素的正確位置了
	a[low]=cur;  
	return low;
}
void qsort(int a[],int low,int high){
	if(low<high){
		int idx=partition(a,low,high);  //確定該元素的正確位置
		qsort(a,low,idx-1);  //遞回左右兩個區間
		qsort(a,idx+1,high);
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	qsort(a,0,4);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

（插播反爬資訊 ）博主CSDN地址：https://wzlodq.blog.csdn.net/

堆排序

以大根堆為例，即根元素是最大的，初始時無序，從下往上（葉節點往根）的方向，將兩個葉子節點中值更大的元素和它的父節點交換，父節點換下來后如果還有子節點（即除了最后一層），則還要比較是否比現在的兩個葉子節點更大，不然選更大的葉節點換上來，依次遞回，

• 時間復雜度 O ( n l o g n ) O(nlogn) O(nlogn)
  n ? 1 n-1 n?1次向下調整操作，每次調整復雜度是 O ( h ) O(h) O(h)即 O ( l o g n ) O(logn) O(logn)，
• 穩定性：不穩定
  可能把后面相同的關鍵字調整到前面，
• 排序趟數是否與原序列有關：有關
  如果有序，每次向下調整的復雜度是 O ( 1 ) O(1) O(1)，

適合頻繁增刪的場景，不必每次重新排序（雖然這里沒給增刪代碼，偷懶），

#include<bits/stdc++.h>
using namespace std;
void adjustheap(int a[], int i, int n){
    for(int j=i*2+1;j<n;){
        if(j+1<n&&a[j]<a[j+1])  //取左右孩子中較大的那個 
    		j++;
        if(a[i]>a[j])break;
        swap(a[i], a[j]);
        //交換后遞回比較與子節點大小 
        i=j;
        j=2*i+1;
    }
}
void makeheap(int a[], int n){  //建堆 
    for(int i=n/2-1; i>=0; i--)//遞回從最后一個父節點開始調整堆
        adjustheap(a,i,n);
}
void heapsort(int a[], int n){
    makeheap(a, n);
    for(int i=n-1; i>=0; i--){
        swap(a[i], a[0]);
        adjustheap(a, 0, i);
    }
}
int main(){
	int a[5]={3,5,1,4,2};
	heapsort(a,5);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

歸并排序

遞回的劃分子區間直到一個元素，然后依次合并子區間，此時每個子區間內部有序，合并程序就是比較兩個子區間的最前面元素，取最小的那個，直到一個子區間取完了，那么再直接加上另一個子區間剩下元素即可，

• 時間復雜度 O ( n l o g n ) O(nlogn) O(nlogn)
  每趟歸并 O ( n ) O(n) O(n)，共需要 O ( l o g n ) O(logn) O(logn)趟歸并，
• 穩定性：穩定
  歸并操作從前往后合并兩個子區間，不會改變相對位置，
• 排序趟數是否與原序列有關：無關
  無論原序列狀態如何，都要劃分到一個元素然后開始歸并，

求逆序對的老常客了，還有可以應用排序超大檔案（eg：記憶體2G，硬碟2T的檔案資料，問你怎么排序），

#include<bits/stdc++.h>
using namespace std;
int b[5];  //輔助陣列 
void merge(int a[],int low,int mid,int high){
	for(int k=low;k<=high;k++)b[k]=a[k];
	int i=low,j=mid+1,k=low;
	//i,j分別表示左右子區間最前面元素下標
	//k表示合并后陣列下標 
	while(i<=mid&&j<=high){
		if(b[i]<=b[j])
			a[k++]=b[i++];
		else a[k++]=b[j++];
	}
	while(i<=mid)a[k++]=b[i++];
	while(j<=high)a[k++]=b[j++]; 
}
void mergeSort(int a[],int low,int high){
	if(low<high){
		int mid=(low+high)/2;  //從中間劃磁區間
		mergeSort(a,low,mid);  //分別歸并左右區間 
		mergeSort(a,mid+1,high); 
		merge(a,low,mid,high);  //歸并 
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	mergeSort(a,0,4);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

基數排序

從每個數的低位向高位遍歷，第二重回圈遍歷每個數，按照該位的數值入隊到對應的位（0~9）里，最后從9到0按加入的順序取出這些數，則完成了一趟資料對第i位的排序，

• 時間復雜度 O ( d ( n + r ) ) O(d(n+r)) O(d(n+r))
  r r r表示基數， d d d是長度， n n n表示個數，
• 穩定性：穩定
  用佇列保證穩定性，
• 排序趟數是否與原序列有關：無關
  按數位和元素個數操作，與序列初試狀態無關，

#include<bits/stdc++.h>
using namespace std;
void counting(int a[],int n,int d,int r){
	queue<int>q[r];  //設定r位佇列
	for(int i=1;i<=d;i++){  //從低到高遍歷位數 
		for(int j=0;j<n;j++){  //遍歷每個數
			int temp=pow(r,i);
			int idx=(a[j]%temp)/(temp/10);  //取出第j個數的第i位 
			q[idx].push(a[j]);  //入隊到對應佇列 
		}
		//一輪結束，從低位往高位按入隊順序把數取出來 
		int k=0;
		for(int j=0;j<r;j++){  //如果要從大到小排序，逆回圈r-1~0 
			while(!q[j].empty()){
				a[k++]=q[j].front();
				q[j].pop();  //出隊 
			}
		}	
	}
}
int main(){
	int a[8]={517,47,402,461,211,985,2,762};
	counting(a,8,3,10);  //個數8，長度3，基數10(0~9)
	for(int i=0;i<8;i++)cout<<a[i]<<" ";
	return 0;
}

• 小結

sort()

就實際編程而言，沒有sort()解決不了的排序問題（如果有那就有吧），它的底層主要是快速排序，原始碼這就不再深究了，下面主要介紹下sort()的用法，
頭檔案是<algorithm>

#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[5]={3,5,1,4,2};
	sort(a,a+5);  //兩個引數分別是起始位置和結束位置 
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

嗯對，就是這么簡單粗暴，
下面再介紹下自定義結構體的復雜排序情況，

#include<bits/stdc++.h>
using namespace std;
struct node{
	string name;
	int grade;
	node(){}
	node(string a,int b){
		name=a;
		grade=b;
	}
	bool operator<(const node&a)const{  //可以自定義小于運算子 
		if(grade==a.grade)  //成績相同，名字升序 
			return name<a.name;
		return a.grade<grade;  //否則按成績降序 
	}
}a[5]; 
bool cmp(node a,node b){  //也可以定義比較函式 
	if(a.name==b.name)  //名字相同，成績降序 
		return a.grade>b.grade;
	return a.name<b.name;  //否則名字升序 
} 
int main(){
	a[0]=node("c",90);
	a[1]=node("b",90);
	a[2]=node("b",95);
	a[3]=node("a",80);
	a[4]=node("da",100);
	sort(a,a+5);  //使用結構體內定義<
	for(int i=0;i<5;i++)
		cout<<a[i].name<<":"<<a[i].grade<<"\n"; 
	cout<<"---------------\n"; 
	sort(a,a+5,cmp);  //使用自定義比較函式
	for(int i=0;i<5;i++)
		cout<<a[i].name<<":"<<a[i].grade<<"\n"; 
	return 0;
}

同樣的也可以對vector<>排序：

#include<bits/stdc++.h>
using namespace std;
struct node{
	string name;
	int grade;
	node(){}
	node(string a,int b){
		name=a;
		grade=b;
	}
	bool operator<(const node&a)const{  //可以自定義小于運算子 
		if(grade==a.grade)  //成績相同，名字升序 
			return name<a.name;
		return a.grade<grade;  //否則按成績降序 
	}
}a[5]; 
bool cmp(node a,node b){  //也可以定義比較函式 
	if(a.name==b.name)  //名字相同，成績降序 
		return a.grade>b.grade;
	return a.name<b.name;  //否則名字升序 
} 
int main(){
	a[0]=node("c",90);
	a[1]=node("b",90);
	a[2]=node("b",95);
	a[3]=node("a",80);
	a[4]=node("da",100);
	vector<node>v;
	for(int i=0;i<5;i++)v.push_back(a[i]);
	sort(v.begin(),v.end());  //起始位置，結束位置，[比較函式] 
	for(int i=0;i<5;i++)
		cout<<v[i].name<<":"<<v[i].grade<<"\n"; 
	cout<<"---------------\n"; 
	sort(v.begin(),v.end(),cmp);  //換湯不換藥 
	for(int i=0;i<5;i++)
		cout<<v[i].name<<":"<<v[i].grade<<"\n"; 
	return 0;
}

附：演算法可視化網站
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

原創不易，請勿轉載（本不富裕的訪問量雪上加霜 ）
博主首頁：https://wzlodq.blog.csdn.net/
來都來了，不評論兩句嗎👀
如果文章對你有幫助，記得一鍵三連?