題目：Heap Sort

連結：https://leetcode.com/problems/sort-an-array/description/

• 等級：中等

解題思路

堆排序是一種基於比較的排序算法，它首先從數組中創建一個最大/最小堆，然後重複從中提取最大/最小元素。提取的元素然後放在排序後的數組的末尾。這個過程重複執行，直到堆為空。

要執行堆排序，我們按照以下步驟進行：

1. 從給定的數組構建一個最大/最小堆。
2. 將根元素與堆的最後一個元素交換位置，並將堆的大小減1。
3. 對根元素進行堆化，以保持堆的性質。
4. 重複執行步驟2和步驟3，直到堆為空。

class Solution {
    public List<Integer> sortArray(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        heapSort(nums);
        for (int i : nums) res.add(i);
        return res;
    }
    private void heapSort(int[] nums) {
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            heapify(nums, i, nums.length - 1);
        }
        for (int i = nums.length - 1; i >= 1; i--) {
            swap(nums, 0, i);
            heapify(nums, 0, i - 1);
        }
    }
    private void heapify(int[] nums, int i, int end) {
        while (i <= end) {
            int l = 2 * i + 1, r = 2 * i + 2;
            int maxIndex = i;
            if (l <= end && nums[l] > nums[maxIndex]) maxIndex = l;
            if (r <= end && nums[r] > nums[maxIndex]) maxIndex = r;
            if (maxIndex == i) break;
            swap(nums, i, maxIndex);
            i = maxIndex;
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

• 時間複雜度：O(n log n)
• 空間複雜度：O(1)

問題: Merge Sort

連結: https://leetcode.com/problems/sort-an-array/description/

• 難度:Medium

方法

合併排序是一種分組排序算法，將數組分成兩半，分別對其進行排序，然後將它們合併在一起。合併的過程將兩個已排序的部分合併成一個已排序的數組。

執行合併排序，我們按照以下步驟進行：

1. 將給定的數組分成兩半。
2. 遞歸地對每一半進行排序。
3. 合併已排序的兩半。

class Solution {
    public List<Integer> sortArray(int[] nums) {
        if (nums == null || nums.length == 0) return new ArrayList<>();
        mergeSort(nums, 0, nums.length - 1);
        List<Integer> res = new ArrayList<>();
        for (int num : nums) {
            res.add(num);
        }
        return res;
    }

    private void mergeSort(int[] nums, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(nums, low, mid);
            mergeSort(nums, mid + 1, high);
            merge(nums, low, mid, high);
        }
    }

    private void merge(int[] nums, int low, int mid, int high) {
        int n1 = mid - low + 1;
        int n2 = high - mid;
        int[] left = new int[n1];
        int[] right = new int[n2];
        for (int i = 0; i < n1; i++) {
            left[i] = nums[low + i];
        }
        for (int j = 0; j < n2; j++) {
            right[j] = nums[mid + 1 + j];
        }
        int i = 0, j = 0, k = low;
        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                nums[k] = left[i];
                i++;
            } else {
                nums[k] = right[j];
                j++;
            }
            k++;
        }
        while (i < n1) {
            nums[k] = left[i];
            i++;
            k++;
        }
        while (j < n2) {
            nums[k] = right[j];
            j++;
            k++;
        }
    }
}

• 時間複雜度: O(n log n)
• 空間複雜度: O(n)