【系列】經典演算法題 ：排序演算法空間

• 2019 年 10 月 4 日
• 筆記

作者 | 程式設計師小吳

來源 | 五分鐘學演算法

題目描述

下述幾種排序方法中，要求記憶體最大的是（）

A、快速排序

B、插入排序

C、選擇排序

D、歸併排序

題目解析

一般對於 排序問題 ，我們遇到的都是考察 時間複雜度 ，很少會去了解它們的 空間複雜度，險些被這道題給繞過去。

這個問題如果對下面這張圖比較了解的話，很快就能選出答案。

• 快速排序的實現採取了遞歸，因此空間複雜度為 O(logn)。
• 插入排序只是藉助一個臨時變數進行交換元素，因此空間複雜度為 O(1)。
• 選擇排序與插入排序差不多，因此空間複雜度為 O(1)。
• 歸併排序需要分配一個大小為 n 的數組，因此空間複雜度為 O(n)。

以，這一題的答案為 D。