本文參照AcWing闫學燦大神的講解，整理了一下排序算法的實作。
算法總結
| 排序算法 | 平均時間複雜度 | 最好情況 | 最壞情況 | 空間複雜度 | 穩定性 |
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 穩定 |
| 選擇排序 | O(n²) | O(n²) | O(n²) | O(1) | 不穩定 |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 穩定 |
| 希爾排序 | O(nlogn) | O(  | O(n²) | O(1) | 不穩定 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n + logn) | 穩定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | 不穩定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩定 |
| 桶排序 | O(n + k) | O(n + k) | O(n²) | O(n + k) | 穩定 |
| 計數排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 穩定 |
| 基數排序 | O(n × m) | O(n × m) | O(n × m) | O(n + m) | 穩定 |
冒泡排序
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void bubbleSort(vector<int> &q){
for(int i = q.size() - 1; i > 0; i--){
bool flag = false;
for(int j = 0; j + 1 <= i; j++){
if(q[j] > q[j+1]){
swap(q[j], q[j+1]);
flag = true;
}
}
if(!flag)
break;
}
}
int main(){
int n;
vector<int> q;
cin >> n;
for(int i = 0, t; i < n; i++){
cin >> t;
q.push_back(t);
}
bubbleSort(q);
for(auto x : q)
cout << x << ' ';
cout << endl;
return 0;
}
十大排序算法（C++實作）
選擇排序
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void selectionSort(vector<int> &q){
for(int i = 0; i < q.size(); i++){
for(int j = i + 1; j < q.size(); j++){
if(q[i] > q[j])
swap(q[i], q[j]);
}
}
}
int main(){
int n;
vector<int> q;
cin >> n;
for(int i = 0, t; i < n; i++){
cin >> t;
q.push_back(t);
}
selectionSort(q);
for(auto x : q)
cout << x << ' ';
cout << endl;
return 0;
}
十大排序算法（C++實作）
插入排序
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void insertionSort(vector<int> &q){
for(int i = 1; i < q.size(); i++){
int t = q[i], j;
for(j = i - 1; j >= 0; j--){
if(q[j] > t)
q[j+1] = q[j];
else
break;
}
q[j+1] = t;
}
}
int main(){
int n;
vector<int> q;
cin >> n;
for(int i = 0, t; i < n; i++){
cin >> t;
q.push_back(t);
}
insertionSort(q);
for(auto x : q)
cout << x << ' ';
cout << endl;
return 0;
}
十大排序算法（C++實作）
希爾排序
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void shellSort(vector<int> &q){
int gap = q.size() / 2;
while(gap){
for(int i = gap; i < q.size(); i += gap){
int t = q[i], j;
for(j = i - gap; j >= 0; j -= gap){
if(q[j] > t)
q[j+gap] = q[j];
else
break;
}
q[j+gap] = t;
}
gap /= 2;
}
}
int main(){
int n;
vector<int> q;
cin >> n;
for(int i = 0, t; i < n; i++){
cin >> t;
q.push_back(t);
}
shellSort(q);
for(auto x : q)
cout << x << ' ';
cout << endl;
return 0;
}
十大排序算法（C++實作）
歸并排序
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void mergeSort(vector<int> &q, int l, int r){
if(l >= r)
return;
int mid = l + r >> 1;
mergeSort(q, l, mid);
mergeSort(q, mid + 1, r);
static vector<int> w;
w.clear();
int i = l, j = mid + 1;
while(i <= mid && j <= r){
if(q[i] > q[j])
w.push_back(q[j++]);
else
w.push_back(q[i++]);
}
while(i <= mid)
w.push_back(q[i++]);
while(j <= mid)
w.push_back(q[j++]);
for(int i : w)
q[l++] = i;
}
int main(){
int n;
vector<int> q;
cin >> n;
for(int i = 0, t; i < n; i++){
cin >> t;
q.push_back(t);
}
mergeSort(q, 0, n - 1);
for(auto x : q)
cout << x << ' ';
cout << endl;
return 0;
}
十大排序算法（C++實作）
快速排序
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdlib.h>
using namespace std;
void quickSort(vector<int> &q, int l, int r){
if(l >= r)
return;
int i = l - 1, j = r + 1, x = q[l + rand() % (r - l + 1)];
while(i < j){
do j--; while(q[j] > x);
do i++; while(q[i] < x);
if(i < j)
swap(q[i], q[j]);
else{
quickSort(q, l, j);
quickSort(q, j + 1, r);
}
}
}
int main(){
int n;
vector<int> q;
cin >> n;
for(int i = 0, t; i < n; i++){
cin >> t;
q.push_back(t);
}
quickSort(q, 0, n - 1);
for(auto x : q)
cout << x << ' ';
cout << endl;
return 0;
}
十大排序算法（C++實作）
堆排序
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void push_down(vector<int>& heap, int size, int u){
int t = u, left = u * 2, right = u * 2 + 1;
if(left <= size && heap[left] > heap[t])
t = left;
if(right <= size && heap[right] > heap[t])
t = right;
if(u != t){
swap(heap[u], heap[t]);
push_down(heap, size, t);
}
}
void push_up(vector<int>& heap, int u){
while(u / 2 && heap[u / 2] < heap[u]){
swap(heap[u / 2], heap[u]);
u /= 2;
}
}
void heapSort(vector<int> &q, int n){
int size = n;
for(int i = 1; i <= n; i++)
push_up(q, i);
for(int i = 1; i <= n; i++){
swap(q[1], q[size]);
size--;
push_down(q, size, 1);
}
}
int main(){
int n;
vector<int> q;
cin >> n;
q.resize(n + 1);
for(int i = 1; i <= n; i++)
cin >> q[i];
heapSort(q, n);
for(int i = 1; i <= n; i++)
cout << q[i] << ' ';
cout << endl;
return 0;
}
十大排序算法（C++實作）
桶排序
桶排序的思想是我們首先要知道所有待排序的數的資料範圍，知道裡面的最大值和最小值各是多少。然後利用最大值和最小值分成若幹個桶（資料區間），将所有待排序的數按照其大小分到這些桶（資料區間）中。在每個桶中分别利用排序算法進行排序，這樣就完成了所有資料的排序。
十大排序算法（C++實作）
計數排序
這裡設所有待排序的數的範圍是從0~100的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void countingSort(vector<int> &q, int n){
vector<int> cnt(101, 0);
for(int i = 0; i < n; i++)
cnt[q[i]]++;
for(int i = 0, k = 0; i <= 100; i++){
while(cnt[i]){
q[k++] = i;
cnt[i]--;
}
}
}
int main(){
int n;
vector<int> q;
cin >> n;
for(int i = 0, t; i < n; i++){
cin >> t;
q.push_back(t);
}
countingSort(q, n);
for(auto x : q)
cout << x << ' ';
cout << endl;
return 0;
}
十大排序算法（C++實作）
基數排序
這裡設所有待排序的數都不超過三位數，也就是說不超過999。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int get(int x, int i){
while(i--)
x /= 10;
return x % 10;
}
void radixSort(vector<int> &q, int n){
vector<vector<int>> cnt(10);
for(int i = 0; i < 3; i++){
for(int j = 0; j < 10; j++)
cnt[j].clear();
for(int j = 0; j < n; j++)
cnt[get(q[j], i)].push_back(q[j]);
for(int j = 0, k = 0; j < 10; j++){
for(int x : cnt[j])
q[k++] = x;
}
}
}
int main(){
int n;
vector<int> q;
cin >> n;
for(int i = 0, t; i < n; i++){
cin >> t;
q.push_back(t);
}
radixSort(q, n);
for(auto x : q)
cout << x << ' ';
cout << endl;
return 0;
}