目錄
Bubble sort 泡沫排序法
【原理】把大泡泡往下沉,小泡泡向上浮。
【複雜度】O(N2)
【練習】a539: 10327 – Flip Sort 【題解】

for (int i=N-2; i>=0; i--){
for (int j=0; j<=i; j++){
if (a[j] > a[j+1]) swap(a[j], a[j+1]);
}
}
Insertion sort 插入排序法
【原理】逐一檢查每個數字,把數字插入合適的位置。
【複雜度】O(N2)

for (int i=1; i<N; i++) {
int key = a[i];
int j = i - 1;
while (key < a[j] && j >= 0) {
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
Selection sort 選擇排序法
【原理】從頭開始檢查每個位置,把它跟其後最小的數字進行對調。
【複雜度】O(N2)

for (int i=0; i<N-1; i++) {
int mn = a[i];
int pos = i;
for (int j=i+1; j<N; j++){
if (a[j] < mn){
mn = a[j];
pos = j;
}
}
swap(a[i], a[pos]);
}