常見的排序演算法有：氣泡排序 (Bubble Sort)、選擇排序 (Selection Sort)、插入排序 (Insertion Sort)、快速排序 (Quick Sort)、合併排序 (Merge Sort)、堆積排序 (Heap Sort)，以下我將分別介紹。
1. 氣泡排序 (Bubble Sort)
氣泡排序：如果這個數字比右邊的大，交換兩位置，使較大的逐漸浮到右側，再縮小範圍進行下一回合。
說明：外層 for(i) 控制回合數（n-1 代表倒數第二個數字就停止，因為 a[j+1] 會比較到最後一個數字），內層 for(j) 控制每一回合的比較次數（n-1-i 代表比較範圍會隨著已經排序好的數量增加而減少）。
時間複雜度：O(n²)。
for(int i=0; i<n-1; i++)
for(int j=0; j<n-1-i; j++)
if(a[j] > a[j+1])
swap(a[j], a[j+1]);2. 選擇排序 (Selection Sort)
選擇排序：在未排序區中找最小值，放置在已排序區的末尾。
舉例：
[5、4、1、2] 最小值=1
1、[4、5、2] 最小值=2
1、2、[5、4] 最小值=4
1、2、4、5。
時間複雜度：O(n2)。
for(int i=0; i<n; i++){
int min_index = i;
for(int j=i+1; j<n; j++){
if(a[j] < a[min_index])
min_index = j;
}
swap(a[i], a[min_index]);
}3. 插入排序 (Insertion Sort)
一開始時已排序區只有一個數字，從尾端往回比較大小，將未排序區的數字插入到已排序區的適當位置。
for(i=1; i<size; i++){
insert = arr[i];
j=i-1; //往回比大小
while(j>=0 && arr[j]>insert){
arr[j+1] = arr[j]; //insert還獨立在外面
j--;
}
arr[j+1] = insert; //while退出時j會-1，所以要+1
}效率：O(n²)
4. 快速排序 (Quick Sort)
效率：O(n log(n))
選一個 pivot 為基準，找出 i 和 j。
i 為由前往後第一個 > pivot 的，j 為由後往前第一個 < pivot 的。
找到 i 和 j 後，如果 i ≤ j，i 與 j 互換。
如果 j 在 i 的左邊或 i 和 j 相同，pivot 與 j 互換，此時 pivot 已排序完畢。
以 pivot 的左半部與右半部分成兩部分，重複以上步驟。
//Quick Sort
#include <stdio.h>
#define size 10
void quicksort(int *arr, int l, int r){
int i=l, j=r+1, tmp;
if(l<r){
while(i<j){
while(arr[++i] < arr[l]);
while(arr[--j] > arr[l]);
if(i>=j) break;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
tmp = arr[j];
arr[j] = arr[l];
arr[l] = tmp;
quicksort(arr, l, j-1);
quicksort(arr, j+1, r);
}
}
int main(){
int arr[size] = {7,1,8,3,5,2,9,6,0,4};
quicksort(arr, 0, size-1);
int i;
for(i=0; i<size; i++)
printf("%d ", arr[i]);
}5. 合併排序 (Merge Sort)
#include <bits/stdc++.h>
using namespace std;
#define size 6
void merge(int *arr, int L, int M, int R){
int left = L; //左半部執行到第幾個
int right = M+1;
int tmp[size], i=L; //i是陣列tmp的索引值
while((left<=M)&&(right<=R)){ //代表還有元素可以合併
if(arr[left]<arr[right])
tmp[i++]=arr[left++];
else tmp[i++]=arr[right++];
}
while(left<=M) //代表還有剩餘元素需要放入陣列tmp
tmp[i++]=arr[left++];
while(right<=R)
tmp[i++]=arr[right++];
for(i=L; i<=R; i++)
arr[i] = tmp[i];
}
void mergesort(int *arr, int L, int R){
int M;
if(L<R){
M = (L+R)/2;
mergesort(arr, L, M); //切割成左半部
mergesort(arr, M+1, R);
merge(arr, L, M, R);
}
}
int main(){
int arr[size] = {3,2,5,1,4,6};
mergesort(arr, 0, size-1);
for(int i=0; i<size; i++)
cout << arr[i] << " ";
}效率：O(n log(n))
參考資料：演算法筆記 – Sort
