// 快速排序
const quickSort = arr => {
    if (arr.length <= 1) {
        return arr
    }
    //  取枢纽下标
    const pivot = Math.floor(arr.length/2)
    //  取枢纽值
    const pivotValue = arr.splice(pivot, 1)[0]
    // 比枢纽小的值放左边数组
    const leftArr = []
    // 比枢纽大的值放右边数组
    const rightArr = []
    // 遍历数组,比枢纽值小放左边数组，否则放右边数组
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivotValue) {
            leftArr.push(arr[i])
        } else {
            rightArr.push(arr[i])
        }
    }
    // 递归以上操作，对左右两个数组进行操作，直到数组长度为1
    return quickSort(leftArr).concat(pivotValue, quickSort(rightArr))
}
// console.log(quickSort([12,2,23,34,13,55,67,88,34,45,8,16]))
// console.log(quickSort([12,-2,23,-34,13,55,67,88,34,45,8,16]))

// 冒泡排序
const bubbleSort = arr => {
    var length = arr.length
    for (let i = length - 1; i  >= 0; i--) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
        }
    }
    return arr
}
// console.log(bubbleSort([12,2,-23,34, 0,13,55,67,88,34,45,8,16]))


// 选择排序
const selectSort = arr => {
    let length = arr.length
    for (let i = 0; i < length; i++) {
        let min = i
        for(let j = min + 1; j < length; j++) {
            if (arr[min] > arr[j]) {
                min = j
            }
        }
        let temp = arr[i]
        arr[i] = arr[min]
        arr[min] = temp
    }
    return arr
}
// console.log(selectSort([12,2,-23,34, 0,13,55,67,88,34,45,8,16]))


// 插入排序
const insertSort = arr => {
    let length = arr.length
    for(let i = 1; i < length; i++) {
        let temp = arr[i]
        let j = i
        while (temp < arr[j-1] && j > 0) {
            arr[j] = arr[j-1]
            j--
        }
        arr[j] = temp
    }
    return arr
}
// console.log(insertSort([12,2,-23,34, 0,13,55,67,88,34,45,8,16]))