912. Sort an Array

Medium

Description

給定整數陣列 nums，將其升序排序並回傳。必須在 O(n log n) 時間複雜度內完成，且盡量使用最少的空間。不能使用內建排序函式。

Example:

Input: nums = [5,2,3,1] Output: [1,2,3,5]

Intuition#

核心思路：要求 O(n log n) 且不用內建排序，Merge Sort 是最穩定的選擇。Quick Sort 在最壞情況下 O(n^2) 可能 TLE，需要隨機 pivot。

Merge Sort：穩定、保證 O(n log n)，但需要 O(n) 額外空間
Quick Sort：平均 O(n log n)，但最壞 O(n^2)（需隨機化 pivot 避免）
Heap Sort：O(n log n) 且 O(1) 空間，但常數因子較大

Approaches#

1: Merge Sort#

概念: 分治法——將陣列一分為二，遞迴排序後合併
時間複雜度: O(n log n) - 保證
空間複雜度: O(n) - 合併時需要暫存陣列

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        if (nums.size <= 1) return nums
        val mid = nums.size / 2
        val left = sortArray(nums.copyOfRange(0, mid))
        val right = sortArray(nums.copyOfRange(mid, nums.size))
        return merge(left, right)
    }

    private fun merge(left: IntArray, right: IntArray): IntArray {
        val result = IntArray(left.size + right.size)
        var i = 0; var j = 0; var k = 0
        while (i < left.size && j < right.size) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++]
            } else {
                result[k++] = right[j++]
            }
        }
        while (i < left.size) result[k++] = left[i++]
        while (j < right.size) result[k++] = right[j++]
        return result
    }
}

⭐2: Quick Sort（隨機 Pivot）#

概念: 隨機選 pivot，將小於 pivot 的放左邊、等於放中間、大於放右邊（三向切分），遞迴排序左右部分
時間複雜度: 平均 O(n log n)，最壞 O(n^2)（隨機化後極不可能）
空間複雜度: O(log n) - 遞迴堆疊

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        quickSort(nums, 0, nums.size - 1)
        return nums
    }

    private fun quickSort(nums: IntArray, lo: Int, hi: Int) {
        if (lo >= hi) return
        // 隨機選 pivot
        val pivotIdx = lo + (Math.random() * (hi - lo + 1)).toInt()
        val pivot = nums[pivotIdx]

        // 三向切分：[lo, lt) < pivot, [lt, gt] == pivot, (gt, hi] > pivot
        var lt = lo; var i = lo; var gt = hi
        while (i <= gt) {
            when {
                nums[i] < pivot -> {
                    nums[i] = nums[lt].also { nums[lt] = nums[i] }
                    lt++; i++
                }
                nums[i] > pivot -> {
                    nums[i] = nums[gt].also { nums[gt] = nums[i] }
                    gt--
                }
                else -> i++
            }
        }
        quickSort(nums, lo, lt - 1)
        quickSort(nums, gt + 1, hi)
    }
}

補充：Heap Sort

使用最大堆的性質，先建堆再逐一取出最大元素放到陣列末尾。O(1) 額外空間。

class Solution {
    fun sortArray(nums: IntArray): IntArray {
        // Build max heap
        for (i in nums.size / 2 - 1 downTo 0) {
            heapify(nums, nums.size, i)
        }
        // Extract elements one by one
        for (i in nums.size - 1 downTo 1) {
            nums[0] = nums[i].also { nums[i] = nums[0] }
            heapify(nums, i, 0)
        }
        return nums
    }

    private fun heapify(nums: IntArray, n: Int, i: Int) {
        var largest = i
        val left = 2 * i + 1
        val right = 2 * i + 2
        if (left < n && nums[left] > nums[largest]) largest = left
        if (right < n && nums[right] > nums[largest]) largest = right
        if (largest != i) {
            nums[i] = nums[largest].also { nums[largest] = nums[i] }
            heapify(nums, n, largest)
        }
    }
}

🔑 Takeaways#

Pattern: 排序演算法實作是面試基本功，必須能手寫 Merge Sort 和 Quick Sort
關鍵技巧: Quick Sort 一定要隨機化 pivot，否則 LeetCode 的測資會卡到 O(n^2)；三向切分（Dutch National Flag）處理大量重複元素特別有效