排序的定義

這個不用說吧
就是根據某個條件對一個數列進行有序的操作
例如要求從小到大排序、從大到小排序等等

排序的分類

比較排序$(Comparison$ $Sorts)$

特點：通過元素間的比較決定順序
時間復雜度下限：$O(n$ $log$ $n)$

排序算法	平均時間復雜度	空間復雜度	穩定性	特點
冒泡排序	$O(n^2)$	$O(1)$	穩定	簡單但慢
選擇排序	$O(n^2)$	$O(1)$	不穩定	每次選最小放前面
插入排序	$O(n^2)$	$O(1)$	穩定	對小規模數據高效
快速排序	$O(n$ $log$ $n)$	$O(logn)$	不穩定	分治思想，實際最快
歸并排序	$O(n$ $log$ $n)$	$O(n)$	穩定	分治+合并，需額外空間
堆排序	$O(n$ $log$ $n)$	$O(1)$	不穩定	利用堆結構

非比較排序$(Non?Comparison$ $Sorts)$

特點：不直接比較元素，利用數值特性
時間復雜度：可突破$O(n$ $log$ $n)$下限

排序算法	時間復雜度	空間復雜度	穩定性	適用場景
計數排序	$O(n+k)$	$O(k)$	穩定	整數且范圍小（$k$為范圍）
桶排序	$O(n+k)$	$O(n+k)$	穩定	數據均勻分布
基數排序	$O(d(n+k))$	$O(n+k)$	穩定	整數按位排序（$d$為位數）

建議

• 通用：快速排序（STL 的 sort）
• 穩定：歸并排序（STL 的 stable_sort）
• 小范圍整數：計數排序
• 數據大：堆排序（避免快排遞歸棧溢出）

注：實際代碼實現需根據數據特點選擇

模板代碼示例

這里給出常用的冒泡排序、選擇排序、快速排序等
內容解釋在代碼注釋里，全是干貨可以直接食用

冒泡排序

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//核心代碼for(int i=1;i<=n-1;i++){//n-1輪排序bool swapped=false;//優化：記錄是否發生交換for(int j=1;j<=n-i;j++){//每輪比較前n-i個元素if(a[j]>a[j+1]){//相鄰元素比較swap(a[j],a[j+1]);//交換swapped=true;}}if(!swapped)break;//本輪無交換說明已有序}for(int i=1;i<=n;i++)cout<<a[i]<<" ";//排序后結果return 0;
}

選擇排序

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//核心代碼for(int i=1;i<=n-1;i++){//n-1輪選擇int minn=i;//記錄最小值位置for(int j=i+1;j<=n;j++){//在未排序部分找最小值if(a[j]<a[minn])minn=j;}swap(a[i],a[minn]);//把最小值放到已排序末尾}for(int i=1;i<=n;i++)cout<<a[i]<<" ";//排序后結果return 0;
}

快速排序

可以用自己寫函數更改排序條件
一般配合結構體使用，下篇文章有講到

#include<iostream>
#include<algorithm>
//sort函數必要頭文件，如果不想加可以自己寫sort
using namespace std;
int a[5000001];//待排序數組
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);//直接調用sort函數排序[1,n]區間for(int i=1;i<=n;i++)cout<<a[i]<<" ";//排序后結果，快排是最簡單的排序~return 0;
}

插入排序

#include<iostream>
using namespace std;
int a[5000001];//待排序數組
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=2;i<=n;i++){//從第二個元素開始!!int key=a[i];//當前要插入的元素int j=i-1;while(j>=1&&a[j]>key){//向前找插入位置a[j+1]=a[j];//元素后移j--;}a[j+1]=key;//插入元素}for(int i=1;i<=n;i++)cout<<a[i]<<" ";//排序后結果return 0;
}

計數排序

#include<iostream>
using namespace std;
const int N=5000001;
const int K=100000;//數據范圍自行調整
int a[N],cnt[K],b[N];
void csort(int n){for(int i=1;i<=n;i++)cnt[a[i]]++;for(int i=1;i<K;i++)cnt[i]+=cnt[i-1];for(int i=n;i>=1;i--)b[cnt[a[i]]--]=a[i];for(int i=1;i<=n;i++)a[i]=b[i];
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];csort(n);for(int i=1;i<=n;i++)cout<<a[i]<<" ";return 0;
}

這個注釋不好寫，講一下

變量定義說明：

• a[]：待排序數組
• cnt[]：計數數組
• b[]：臨時存儲排序結果
• K：數據最大值范圍

流程：

• 統計每個元素出現次數（cnt[a[i]]++）
• 計算前綴和確定元素位置（cnt[i]+=cnt[i-1]）
• 反向填充保證穩定性（b[cnt[a[i]]--]=a[i]）
• 回寫到原數組（a[i]=b[i]）

注意事項：

• 僅適用于非負整數排序
• 數據范圍K需要提前確定
• 時間復雜度：O(n+K)（線性時間）

例題實戰

$【題目傳送門】$

P1177 【模板】排序

題目描述

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

輸入格式

第一行為一個正整數 $N$。

第二行包含 $N$ 個空格隔開的正整數 $a_i$，為你需要進行排序的數。

輸出格式

將給定的 $N$ 個數從小到大輸出，數之間空格隔開，行末換行且無空格。

輸入輸出樣例 #1

輸入 #1

5
4 2 4 5 1

輸出 #1

1 2 4 4 5

說明/提示

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

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

分析

簡單的排序模板題，范圍不大
可以直接用最簡單的$sort$秒過
沒看懂的可以看上方代碼↑有注釋解釋
直接上代碼↓

例題代碼

#include <iostream>
#include <algorithm>
using namespace std;
int n,a[1000005];//數組范圍10^5
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);//快排for(int i=1;i<=n;i++)cout<<a[i]<<" ";return 0;
}

題單推薦

$排序?題單$
例題和題單來自$洛谷$

~ $完結撒花$ ~

附：這篇比較簡單，之前忘記講了
之前漏了很多，把基礎補回來之后再講后面的例題
下一篇預告：遞推遞歸或者結構體