LeetCode-912. Sort an Array

LeetCode-912. Sort an Array

難度: medium

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

 

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation:  Note that the values of nums are not necessairly unique.

Constraints:

• 1 <= nums.length <= 5 * 104.
• -5 * 104 <= nums[i] <= 5 * 104

解題流程

1. 先看懂題目想描述甚麼情境
2. 開始想像程式運作該經過哪些流程
3. 將經過的流程所需的判斷跟細節列出
4. 實作列出的流程

先看懂題目想描述甚麼情境

開始想像程式運作該經過哪些流程

將經過的流程所需的判斷跟細節列出

實作列出的流程

typescript

快速排序版

function sortArray(nums: number[]): number[] {

    function partition(expArray, start, end) {
        let pivot = start;
        let pivotNum = expArray[pivot];
        while(start < end) {

            while(start < end && pivotNum <= expArray[end]) {
                end--;
            }

            while(start < end && pivotNum >= expArray[start]) {
                start++;
            }

            if(start < end) {
                swap(expArray, start, end);
            }
        }

        swap(expArray, start, pivot);
        return start;
    }

    function quickSort(expArray, start, end) {
        if(start < end) {
            const partitionIndex = partition(expArray, start, end);
            quickSort(expArray, start, partitionIndex - 1);
            quickSort(expArray, partitionIndex + 1, end);
        }
    }
    function swap(expArray, start, end ) {
        const temp = expArray[start];
        expArray[start] = expArray[end];
        expArray[end] = temp;
    }
    quickSort(nums, 0 , nums.length - 1);
    return nums;
};

感謝閱讀，如果有錯誤或是講得不清楚的部分，再請留言指教