# 经典排序算法-05-快速排序

/**
 * 大多数情况下的最优排序算法
 * 基于冒泡排序的升级改进
 * 分而治之的排序思想
 * @param {Array} arr 
 */
function quickSort(arr) {
    if(!arr.length) return []
    if(arr.length === 1) return arr

    var index = Math.floor(arr.length/2)

    var x = arr.splice(index, 1)
    var left = []
    var right = []
    for (let i = 0; i < arr.length; i++) {
        const num = arr[i];
        if(num < x) {
            left.push(num)
        }else{
            right.push(num)
        }
    }
    left = quickSort(left)
    right = quickSort(right)
    return left.concat(x, right)
}

const nums = [3,5,9,7,4,2,10]
const ret = quickSort(nums)
console.log(ret)