題目網址：https://leetcode.cn/problems/sort-an-array/

題意：給一整數 array nums, 將其按升序排列後並返回它。

Solution 1：(TLE 無法通過)

想法：利用 Bubble Sort, 每次比較相鄰兩元素, 如果第一個比第二個大, 則交換。每一回合結束後, 未排序中的最大值會浮到最右邊

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        const int n = nums.size();

        // 總共 (n - 1) 回合
        for (int i = 0; i < n - 1; ++i) {
            bool swapped = false;

            // 第 i 回合只需 compare (n - 1 - i) 次
            for (int j = 0; j < n - 1 - i; ++j) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums[j], nums[j + 1]);
                    swapped = true;
                }
            }

            // 若無 swap 則結束
            if (swapped == false) {
                return nums;
            }
        }

        return nums;
    }
};
  • time：$O(n^2)$. ➔ Bubble Sort 的 avg case 時間複雜度
    • $T(n) = T(n - 1) + \dfrac{n}{2}$, 其中 $\dfrac{n}{2}$ 是平均 swap 的次數
    • 平均 swap 的次數 : $\dfrac{[1 + 2 + … +(n-1)]}{(n-1)} = \dfrac{n(n-1)}{2} \cdot \dfrac{1}{(n-1)} = \dfrac{n}{2}$
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：利用 Merge Sort

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

private:
    void mergeSort(vector<int>& nums, const int low, const int high){
        if (low < high) {
            const int mid = low + (high - low) / 2;
            mergeSort(nums, low, mid);
            mergeSort(nums, mid + 1, high);
            merge(nums, low, mid, high);
        }
    }

    void merge(vector<int>& nums, const int low, const int mid, const int high){
         if (low < high) {
            int left = low, right = mid + 1, len = high - low + 1;
            vector<int> sorted(len, 0);

            int k = 0;
            while (left <= mid && right <= high) {
                sorted[k++] = (nums[left] < nums[right]) ? nums[left++] : nums[right++];
            }

            while (left <= mid) {
                sorted[k++] = nums[left++];
            }

            while (right <= high) {
                sorted[k++] = nums[right++];
            }

            for (k = 0; k < len; ++k) {
                nums[low + k] = sorted[k];
            }
        }
    }
};
  • time：$O(n \cdot log(n))$ ➔ Merge Sort 的時間複雜度, $T(n) = 2 \cdot T(\dfrac{n}{2}) + O(n)$
    • 每回合的合併需要花：$O(n)$
    • 回合數：$O(log(n))$
  • space：$O(n)$ ➔ $O(n + log(n))$
    • $O(n)$：merge 後的 sorted 長度最多為 n
    • $O(log(n))$：取決於遞迴深度, 最大遞迴深度為 log(n)

Solution 3：(TLE 無法通過)

想法：利用 Selection Sort, 每一回合中從第 (i + 1) ~ n 筆中找最小值, 並和第 i 筆做 swap

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        const int n = nums.size();
        int minIndex = 0;

        // 做 n - 1 回合
        for (int i = 0; i < n - 1; ++i) {
            minIndex = i;

            // 每一回合從未排序的 array 中找出最小值
            for (int j = i + 1; j < n; ++j) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }

            swap(nums[i], nums[minIndex]);
        }

        return nums;
    }
};
  • time：$O(n^2)$ ➔ Selection Sort 的 avg case 時間複雜度
    • $T(n) = T(n - 1) + O(n)$, 其中 $O(n)$ 是從未排序的 array 中找出最小值的時間複雜度
  • space：$O(1)$ ➔ 只需常數空間

Solution 4：(TLE 無法通過)

想法：利用 Insertion Sort

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        const int n = nums.size();

        // 做 n - 1 回合
        for (int i = 1; i < n; ++i) {
            if (nums[i] >= nums[i - 1]) {
                continue;
            }

            // 找出 nums[i] 在前面 0 ~ (i - 1) sorted array 中要插入的 idx
            const int idx = binarySearch(nums, 0, i - 1, nums[i]);

            // 將 nums[i] 插入到 idx
            insert(nums, idx, i);
        }
        return nums;
    }

private:
    int binarySearch(const vector<int>& nums, int left, int right, const int target){
        while (left <= right) {
            const int mid = left + (right - left) / 2;
            if (target < nums[mid]) { // mid 右側元素皆 > target, 故往左邊搜尋
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    void insert(vector<int>& nums, const int idx, const int i){
        const int tmp = nums[i]; // 先記住要插入的數

        // 將 idx ~ (i - 1) 的數往後移一位(順序必須由後往前, 不然會蓋掉後面的數)
        for (int k = i; k >= idx + 1; --k) {
            nums[k] = nums[k - 1];
        }

        nums[idx] = tmp;
    }
};
  • time：$O(n^2)$ ➔ Insertion Sort 的 avg case 時間複雜度
    • $T(n) = T(n - 1) + [O(log(n)) + O(n)]$ ➔ $T(n) = T(n - 1) + O(n)$
    • 其中 $O(log(n))$ 是 binary search 的時間複雜度, $O(n)$ 是 insert 的時間複雜度
  • space：$O(1)$ ➔ 只需常數空間