(Day 13) 選擇排序 (Selection Sort)
選擇排序 (Selection Sort) 是一種簡單直觀的排序演算法。核心概念: 每一輪從尚未排序的元素中挑出最小（或最大）者，放到目前應在的位置，一直重複直到完成。可以把它想成「選拔賽」: 第一輪選出最優放第一名，第二輪從剩下的人選次優放第二名，依此類推。
(Day 12) 氣泡排序 (Bubble Sort)
目錄
終於進入演算法的部分，預計會介紹 3~4 個很常見的排序演算法，所以光排序這個主題就會用掉一些篇幅，今天除了介紹 Bubble Sort 外，會先簡單介紹一下排序，讓各位讀者更好地認識排序演算法。
排序概述
排序 (Sorting) 是演算法中最基礎且重要的主題之一，目的是將一組資料依照特定順序 (通常是從小到大或從大到小) 排列。而排序的過程中，資料的移動方式，資料的移動方式可以分為直接移動與邏輯移動:
- 直接移動: 直接交換儲存資料的位置。
- 邏輯移動: 不會移動資料儲存位置，僅改變資料的指標值。
而排序又可以依照使用的記憶體種類區分:
- 內部排序: 排序的資料量小，可以直接在記憶體內完成。
- 外部排序: 排序的資料量大，無法直接在記憶體內完成，而必須使用到輔助記憶體 (e.g. 硬碟)。
針對內部/外部排序常見的演算法如下:
- 內部排序: 氣泡排序、選擇排序、插入排序、合併排序 … 等。
- 外部排序: 直接合併排序、k 路合併排序 … 等。
氣泡排序
氣泡排序又稱交換排序法，原理如下:
- 從第一個元素開始，比較相鄰元素大小，若大小順序有誤，則對調後再進行下一個元素比較。
- 經過一次掃描後，可以確保最後一個元素是位於正確的順序。
假設題目: 使用氣泡排序法將數列 [16, 25, 39, 27, 12, 8, 45, 63] 排序，直接操作一次:
data = [16, 25, 39, 27, 12, 8, 45, 63]
n = len(data)
for i in range(n-1):
for j in range(n-1-i):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
print(data)
這個程式很簡單就是不斷地交換而已，其實上面的是標準版版本的 Bubble Sort，我以前不知道為什麼很容易忘記，我個人比較喜歡下面這個版本:
data = [16, 25, 39, 27, 12, 8, 45, 63]
left = 1
right = len(data) - 1
while right > 0:
if data[left-1] > data[left]:
data[left], data[left-1] = data[left-1], data[left]
if left < len(data) - 1:
left += 1
else:
left = 1
right -= 1
print(data)
這個版本是我自己改的，因為我個人在解演算法題目，都一律先用雙指針想想看能不能解，雖然這個版本符合 Bubble Sort 的核心概念，而且兩個版本的時間複雜度跟空間複雜度都一樣，但是並不是標準版本，所以在考試的時候最好還是寫標準版，不然可能會被算錯。
結語
氣泡排序 (Bubble Sort) 是最基礎的排序演算法之一，它的核心概念非常直觀: 不斷比較相鄰元素，並將最大 (或最小) 的元素一點一點「冒泡」到正確的位置。
然而，Bubble Sort 的效率並不高:
- 時間複雜度: 平均與最壞情況皆為 $O(n^2)$。
- 空間複雜度: 僅需 $O(1)$ 額外空間。
- 穩定性: 屬於穩定排序，當兩個元素相等時，排序後仍保持原來的相對順序。
雖然在實務中，幾乎不會有人真的用 Bubble Sort 去處理大型資料，但它的價值在於:
- 幫助初學者理解排序演算法的基本思路。
- 讓我們認識「交換排序法」的運作模式。
- 建立「效能比較」的基準，因為後續的排序演算法 (如 選擇排序、插入排序、快速排序) 都會以它作為參照點，展現出更佳的效率。
補充
剛好手邊有 code，也因為資料結構或演算法很多原文書都是用 C 語言為主，這邊補出 C 語言與 Java 的版本:
#include<stdio.h>
int main() {
int data[] = {16, 25, 39, 27, 12, 8, 45, 63};
int lenData = sizeof(data) / sizeof(data[0]);
for (int i = 0; i < lenData - 1; i++) {
for (int j = 0; j < lenData - 1 - i; j++) {
int temp = 0;
if (data[j] > data[j+1]) {
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
for (int i = 0; i < lenData; i++) {
printf("%d ", data[i]);
}
return 0;
}
Java 版本的 Bubble Sort:
package io.twcch;
public class Demo {
public static void main(String[] args) {
int[] ints = {16, 25, 39, 27, 12, 8, 45, 63};
for (int i = 0; i < ints.length - 1; i++) {
for (int j = 0; j < ints.length - 1 - i; j++) {
int temp = 0;
if (ints[j] > ints[j+1]) {
temp = ints[j];
ints[j] = ints[j+1];
ints[j+1] = temp;
}
}
}
for (int i = 0; i < ints.length; i++) {
System.out.print(ints[i] + " ");
}
}
}