個人主頁：strive-debug

排序算法精講：從理論到實踐

?一、排序概念及應用

?1.1 基本概念 ?

**排序**：將一組記錄按照特定關鍵字（如數值大小）進行遞增或遞減排列的操作。

?1.2 常見排序算法分類

?
- **簡單低效型**：直接插入排序、冒泡排序、選擇排序 ?
- **高效優化型**：希爾排序、快速排序、歸并排序、堆排序 ?

---

二、基礎排序算法實現

?2.1 插入排序家族

?2.1.1 直接插入排序

核心思想：將待排元素逐個插入已有序序列中。 ?

void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end+1] = tmp;}
}

我的理解（如圖所示）：

**特性分析**： ?
?**接近有序時效率高** ?
?時間復雜度：O(N^2)
?空間復雜度：O(1)

?2.1.2 希爾排序（優化版插入排序）

**優化策略**：通過分組增量（gap）預排序逐步逼近全局有序。 ?

void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//推薦寫法：除3gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if(arr[end] > tmp){ arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

我的理解（如圖所示）：

?

**特性分析**： ?
?**突破O(N^2)的時間瓶頸** ?
?時間復雜度：約 O(N^{1.3})?
?空間復雜度：O(1)

---

2.2 選擇排序

直接選擇排序
**核心思想**：每輪選取最小/最大值固定到序列兩端。 ?

void SelectSort(int* arr, int n)
{int begin = 0, end = n - 1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin; i <= end; i++)//end=n-1,不是n{if (arr[i] > arr[maxi]){maxi = i;//不是arr[i]}if (arr[i] < arr[mini]){mini = i;}}//要先判斷如果maxi在開頭的話，就是發生來回替換的情況if (maxi == begin){maxi = mini;}//循序不能亂Swap(&arr[mini], &arr[begin]);Swap(&arr[maxi], &arr[end]);//不要忘記讓end和begin，這是一個while循環end--;begin++;}
}

我的理解（如圖所示）：

---

?2.3 交換排序

冒泡排序
經典實現+提前終止優化： ?
?

void BubbleSort(int* arr, int n)
{int exchange = 0;for (int i = 0; i < n; i++){for (int j = 0; j < n - 1 - i; j++){if (arr[j] > arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){break;}}
}

**適用場景**： ?
?**教學演示為主，實際工程較少使用** ?
?時間復雜度：O(N^2)??

---

三、算法對比總結

| 算法 ? ? ? ? | 時間復雜度 ? ? ? | 空間復雜度 | 穩定性 | 適用場景? ? ? ? ? ?? |
|--------------|------------------|------------|--------|------------------------|
| 直接插入排序 |O(N^2)? ? ??| O(1)???| ?? ? ? ?| 小規模或接近有序數據 ? |
| 希爾排序? ? ? ? |O(N^{1.3}) |O(1)? ? | ?? ? ? ?| 中等規模數據? ? ? ? ? ? ? ? ?|
| 選擇排序? ? ? ? |O(N^2)??? ? | O(1)? ?| ?? ? ? ?| 教學演示? ? ? ? ? ? ? ? ? ? ? ? ?|
| 冒泡排序? ? ? ? |O(N^2)? ? ? | O(1)? ?| ?? ? ? ?| 理解交換思想? ? ? ? ? ? ? ? ?|

---

?**四、下篇預告**
**《高階排序算法：分治思想與性能突破》** ?
- ?**快速排序的三種分區策略** ?
- ?**歸并排序的遞歸與非遞歸實現** ?
- ?**堆排序與優先隊列的深度關聯**

---