題目：insertion sort

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

• 等級：Easy

解題思路

1. 使用index紀錄陣列位置
2. 迴圈判斷取得的值大於index位置的值，就將數值放在index位置後．

class Solution {
    public List<Integer> sortArray(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        insertionSort(nums);
        for (int i : nums) res.add(i);
        return res;
    }
    private void insertionSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j >= 1; j--) {
                if (nums[j] >= nums[j - 1]) break;
                swap(nums, j, j - 1);
            }
        }
    }
    private void swap(int[] nums, int i, int j) {
				int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

• Time complexity: O(n^2)
• Space complexity: O(n)

題目：select sort

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

• 等級：Easy

解題思路

選擇排序演算法通過反覆從未排序的部分中找到最小元素並將其與未排序部分的開始元素進行交換來對數組進行排序。

class Solution {
    public List<Integer> sortArray(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        selectionSort(nums);
        for (int i : nums) res.add(i);
        return res;
    }
    private void selectionSort(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                swap(nums, i, minIndex);
            }
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

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