爲什麼要關注排序算法的內存消耗？¶

在計算機科學中，排序是最基礎也最常用的操作之一。我們不僅關心排序的快慢（時間複雜度），還關心排序過程中消耗多少額外的內存空間——這就是“空間複雜度”。想象一下，如果你要在手機內存有限的情況下對大量數據排序，選擇一個“內存貪婪”的算法可能導致程序崩潰，而一個“內存友好”的算法能讓排序順利完成。所以，理解不同排序算法的空間消耗，是寫出高效代碼的關鍵。

什麼是空間複雜度？¶

空間複雜度描述的是算法在運行過程中所需的額外存儲空間與輸入數據規模 \( n \) 的關係。它用大O符號（比如 \( O(1) \)、\( O(n) \)）來表示，其中 \( n \) 是輸入數據的大小（如數組元素個數）。

舉個例子：
- \( O(1) \)：額外空間是“常數”，不隨數據量 \( n \) 變化。比如排序時只需要一個臨時變量交換元素。
- \( O(n) \)：額外空間與數據量 \( n \) 成正比。比如需要一個大小爲 \( n \) 的數組輔助排序。
- \( O(\log n) \)：額外空間隨數據量的對數增長，通常來自遞歸調用的棧深度。

常見排序算法的空間複雜度分析¶

1. 原地排序（空間複雜度 \( O(1) \)）¶

冒泡排序、選擇排序、插入排序 都屬於“原地排序”——排序過程中不需要額外的數組或數據結構，僅通過交換元素位置完成排序。

• 冒泡排序：每次比較相鄰元素，交換時用一個臨時變量（比如 temp）存儲待交換的元素，額外空間是常數 \( O(1) \)。
• 選擇排序：每次找到最小元素與未排序部分的第一個元素交換，同樣只需要一個臨時變量，空間複雜度 \( O(1) \)。
• 插入排序：將元素插入到已排序部分的合適位置，需要一個臨時變量存儲當前元素，移動元素時不佔用額外空間，空間複雜度 \( O(1) \)。

2. 歸併排序（空間複雜度 \( O(n) \)）¶

歸併排序採用“分治法”：先將數組分成兩半，分別排序，再合併結果。合併過程需要額外的數組空間：

• 例如，將數組 [3,1,4,2] 分成 [3,1] 和 [4,2]，分別排序後得到 [1,3] 和 [2,4]，再合併爲 [1,2,3,4]。
• 合併時需要一個臨時數組（比如 temp）存儲合併後的結果，該數組大小爲 \( n \)（原數組長度），因此空間複雜度是 \( O(n) \)。

3. 快速排序（空間複雜度 \( O(\log n) \)）¶

快速排序也是分治法，核心是“分區”：選擇一個基準元素，將數組分爲“小於基準”和“大於基準”兩部分，再遞歸排序子數組。

• 快速排序是原地分區的：不需要額外數組，僅通過交換元素實現分區。
• 額外空間主要來自遞歸調用的“棧空間”：遞歸深度平均爲 \( \log n \)（理想情況），最壞情況（如已排序數組）爲 \( n \)，但通常平均空間複雜度記爲 \( O(\log n) \)。

4. 堆排序（空間複雜度 \( O(1) \)）¶

堆排序利用“堆”數據結構，將數組視爲完全二叉樹，通過構建大頂堆/小頂堆實現排序。

• 堆排序在原數組上調整堆結構，不需要額外數組，僅需交換元素，因此空間複雜度爲 \( O(1) \)。

如何選擇考慮空間的排序算法？¶

• 內存有限時：優先選擇原地排序算法（冒泡、選擇、插入、堆排序），它們空間複雜度 \( O(1) \)，對內存要求低。
• 內存充足且需要穩定排序：歸併排序是穩定的（相等元素相對位置不變），且排序後數據有序，適合需要穩定排序且內存足夠的場景（空間複雜度 \( O(n) \)）。
• 追求平均性能：快速排序平均時間複雜度 \( O(n \log n) \)，空間複雜度 \( O(\log n) \)，是多數編程語言標準庫排序（如 C++ 的 sort）的選擇。

總結¶

空間複雜度是衡量排序算法“內存友好度”的關鍵指標：
- 原地排序（冒泡、選擇、插入、堆排序）空間消耗最小，爲 \( O(1) \)；
- 歸併排序需要 \( O(n) \) 額外空間，但穩定且易於理解；
- 快速排序平均空間複雜度 \( O(\log n) \)，適合大多數實際場景。

理解不同算法的空間特性，能幫助我們在時間與空間之間找到平衡，寫出更高效的代碼。