快速排序

Out-Place（空间复杂度高）

Out-Place实现原理

易理解，但空间复杂度高

快速排序用的是分治的思想

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。
2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

Out-Place代码实现

/**
 * 快速排序
 */
function quickSortOutPlace(arr) {

    function sort(nums) {
        if (!nums.length) { // 递归终止条件
            return []
        }
        // 先找分界值，然后比分界值小的放左边数组，大的放右边
        let x = nums.shift() // 分界值
        // 定义了两个数组，空间复杂度较大
        let leftArr = [] 
        let rightArr = []
        while (nums.length) {
            let n = nums.shift()
            if (n < x) {
                leftArr.push(n)
            } else {
                rightArr.push(n)
            }
        }
        return [...sort(leftArr), x, ...sort(rightArr)]
    }

    return sort(arr)
}

console.log(quickSortOutPlace([4,5,2,3,1]))

In-Place（空间复杂度低）

In-place实现原理

所谓快速排序，就是分为三步走：

第一步：选择第一个数字分离出来为基数

第二步：然后将序列中大于基数的放在基数右边，小于基数的放在基数的左边

第三步：然后对基数的左边和右边两个序列重复第二步和第三步

In-Place代码实现

/**
 * 快速排序
 * in-place，空间复杂度低
 */
function quickSortInPlace(arr) {

    // 对区间[start, end]排序
    function sortInPlace(nums, start, end) {
        if (start > end) { // 递归结束条件
            return
        }

        // 1.选择第一个数作为基数
        let x = nums[start]
        // 2.定义两根指针
        let i = start
        let j = end
        // 3.注意一定是j先移动，j遇到比基数小的元素就停下来，然后把元素值赋给i的元素；
        // 然后i移动，遇到比基数大的元素就停下来，然后把元素值赋给j；
        // 然后j移动...以此类推
        // 到i==j时，这个位置就是基数的位置
        while (i < j) {
            // 注意一定是j先移动，遇到比基数小的元素就停下来
            while (i < j && nums[j] > x) {
                j--
            }
            // 把元素值赋给i的元素
            nums[i] = nums[j]

            // 然后到i移动
            while (i < j && nums[i] < x) {
                i++
            }
            // 把元素值赋给j的元素
            nums[j] = nums[i]
        }
        // 最后i==j时，就是基数的位置
        nums[i] = x

        // 然后把基数左右两部分继续递归排序
        sortInPlace(nums, start, i - 1) // 基数左边部分
        sortInPlace(nums, i + 1, end) // 基数右边部分

        return nums
    }

    return sortInPlace(arr, 0, arr.length - 1)
}