Medium
912. Sort an Array
arraydivide-and-conquersortingheap-priority-queuemerge-sortbucket-sortradix-sortcounting-sort
解題說明
Sort an Array
題目描述:
給定一個整數陣列 nums,將其按升序排列後返回。要求不使用內建排序函數,且時間複雜度為 O(n log n)。
解題思路: **合併排序(Merge Sort)**是最穩定的 O(n log n) 演算法,不受輸入分佈影響:
- 分割:將陣列從中間切成左右兩半。
- 遞迴排序:分別對左右兩半遞迴排序。
- 合併:使用雙指標將兩個已排序的子陣列合併成一個有序陣列。
合併排序是穩定排序,最差情況也是 O(n log n),非常適合本題。
注意:快速排序雖然平均 O(n log n),但最差 O(n^2),在 LeetCode 的某些測試案例中會 TLE(尤其是已排序或大量重複元素的情況),除非使用隨機 pivot 或三路劃分。
C++ 解法
複雜度分析
時間複雜度:O(n log n) — 遞迴深度 log n,每層合併操作為 O(n)。
空間複雜度:O(n) — 合併時需要輔助陣列,加上遞迴棧深度 O(log n)。
虛擬碼
1. mergeSort(nums, left, right): a. If left >= right, return. b. mid = (left + right) / 2. c. mergeSort(nums, left, mid). d. mergeSort(nums, mid + 1, right). e. merge(nums, left, mid, right). 2. merge(nums, left, mid, right): a. Create temporary array. b. Use two pointers i = left, j = mid + 1. c. Compare and copy smaller element to temp. d. Copy remaining elements. e. Copy temp back to nums[left..right].
其他解法
隨機化快速排序 + 三路劃分:O(n log n) 平均時間、O(log n) 空間。隨機選 pivot 避免最差情況,三路劃分(Dutch National Flag)高效處理大量重複元素。但最差情況仍為 O(n^2)。
堆排序:O(n log n) 時間、O(1) 空間。原地排序且最差情況有保證,但實際常數較大且不穩定。
基數排序:O(n * d) 時間、O(n) 空間,其中 d 為數字位數。需要處理負數(偏移),適用於值域有限的整數排序。
延伸思考
- 快速排序在哪些輸入模式下會退化到 O(n^2)?隨機化 pivot 如何解決?
- 合併排序是穩定的,而堆排序不穩定。在什麼應用場景下穩定性很重要?
- 如何實現原地合併排序(In-place Merge Sort),使空間複雜度降到 O(log n)?