以下是常見排序算法的總結及C語言實現，包含時間復雜度、空間復雜度和穩定性分析：

---

1. 冒泡排序 (Bubble Sort)

思想：重復比較相鄰元素，將較大元素向后移動。
時間復雜度：O(n2)（最好O(n)，最壞O(n2))
空間復雜度：O(1)
穩定性：穩定

void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int swapped = 0;for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交換相鄰元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = 1;}}if (!swapped) break; // 無交換說明已有序}
}

---

2. 選擇排序 (Selection Sort)

思想：每次選擇未排序部分的最小值，放到已排序序列末尾。
時間復雜度：O(n2)
空間復雜度：O(1)
穩定性：不穩定（交換可能破壞順序）

void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int minIdx = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIdx]) {minIdx = j;}}// 將最小值交換到當前位置int temp = arr[i];arr[i] = arr[minIdx];arr[minIdx] = temp;}
}

---

3. 插入排序 (Insertion Sort)

思想：將未排序元素逐個插入已排序序列的合適位置。
時間復雜度：O(n2)（最好O(n)）
空間復雜度：O(1)
穩定性：穩定

void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;// 將大于key的元素后移while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}

---

4. 希爾排序 (Shell Sort)

思想：改進的插入排序，通過分組增量逐步減少間隔排序。
時間復雜度：O(n log n) ~ O(n2)
空間復雜度：O(1)
穩定性：不穩定

void shellSort(int arr[], int n) {for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}

---

5. 歸并排序 (Merge Sort)

思想：分治法，遞歸拆分數組后合并有序子序列。
時間復雜度：O(n log n)
空間復雜度：O(n)
穩定性：穩定

// 合并兩個有序數組
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int L[n1], R[n2];for (int i = 0; i < n1; i++) L[i] = arr[left + i];for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) arr[k++] = L[i++];else arr[k++] = R[j++];}while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}// 遞歸排序
void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}

---

6. 快速排序 (Quick Sort)

思想：分治法，選取基準值將數組分為兩部分遞歸排序。
時間復雜度：O(n log n)（最壞O(n2)）
空間復雜度：O(log n)（遞歸棧）
穩定性：不穩定

// 分區函數
int partition(int arr[], int low, int high) {int pivot = arr[high]; // 選擇最后一個元素為基準int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;// 交換元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 將基準放到正確位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;
}void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}

---

7. 堆排序 (Heap Sort)

思想：利用最大堆性質，將堆頂元素（最大值）與末尾交換后調整堆。
時間復雜度：O(n log n)
空間復雜度：O(1)
穩定性：不穩定

void heapify(int arr[], int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest]) largest = left;if (right < n && arr[right] > arr[largest]) largest = right;if (largest != i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}
}void heapSort(int arr[], int n) {// 構建最大堆for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);// 逐個提取最大值for (int i = n - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}
}

---

算法對比表

排序算法	平均時間復雜度	最好情況	最壞情況	空間復雜度	穩定性
冒泡排序	O(n2)	O(n)	O(n2)	O(1)	穩定
選擇排序	O(n2)	O(n2)	O(n2)	O(1)	不穩定
插入排序	O(n2)	O(n)	O(n2)	O(1)	穩定
希爾排序	O(n log n)	O(n log2 n)	O(n2)	O(1)	不穩定
歸并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	穩定
快速排序	O(n log n)	O(n log n)	O(n2)	O(log n)	不穩定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不穩定

---

使用建議

• 小規模數據：插入排序（簡單且穩定）

• 中等規模：希爾排序（無需額外空間）

• 大規模數據：快速排序（平均性能最優）

• 需要穩定性：歸并排序（穩定且O(n log n)）

• 內存限制：堆排序（原地排序）

實際應用中常結合多種算法（如快速排序+插入排序）。