/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */

/**
 * 解法一：快速排序
 * 思路：
 * （1）快速排序的主要思想是通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小，
 * （2）然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序。
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(h)，其中 h 为快速排序递归调用的层数。我们需要额外的 O(h) 的递归调用的栈空间，
 * 由于划分的结果不同导致了快速排序递归调用的层数也会不同，最坏情况下需 O(n) 的空间，最优情况下每次都平衡，
 * 此时整个递归树高度为 logn，空间复杂度为 O(logn)。
 */
export function MySort(arr: number[]): number[] {
    const len = arr.length
    if (len === 0) return arr

    const midIndex = Math.floor(len / 2)
    const midValue = arr.splice(midIndex, 1)[0]

    const left: number[] = []
    const right: number[] = []

    // 注意： splice 会修改原数组，所以用 arr.length
    for (let i = 0; i < arr.length; i++) {
        const n = arr[i]
        if (n < midValue) {
            left.push(n)
        } else {
            right.push(n)
        }
    }
    return MySort(left).concat([midValue], MySort(right))
}

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview