912 排序数组.md

912 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

**输入：**nums = [5,2,3,1] 输出：[1,2,3,5]

示例 2：

**输入：**nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]

快速排序递归

function sortArray(nums: number[]): number[] {
    if (nums.length <= 1) return nums
    const pivotIndex = Math.floor(nums.length / 2)
    const pivot = nums.splice(pivotIndex, 1)[0]
    const left = []
    const right = []
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] < pivot) left.push(nums[i])
        else right.push(nums[i])
    }
    return [...sortArray(left), pivot, ...sortArray(right)]
};

冒泡排序非递归

function sortArray(nums: number[]): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
            }
        }
    }
    return nums
};