SOURCE

// 经典快排
const swap = (arr, i,j) => {
    const temp = arr[j]
    arr[j] = arr[i]
    arr[i] = temp
} 


let quickSort = (arr, left, right) => {
    if (left < right) {
        let pivot = right
        let partitionIndex = partition(arr, pivot, left, right)
        quickSort(arr, left, partitionIndex - 1 < left ? left : partitionIndex - 1)
        quickSort(arr, partitionIndex + 1 > right ? right : partitionIndex + 1, right)
    }
}

const partition = (arr, pivot, left,right) => {
    const pivotVal = arr[pivot]
    let startIndex = left
    for (let i = left; i < right; i++) {
        // 小-》大
        // if (arr[i] < pivotVal) {
        //     swap(arr,i,startIndex)
        //     startIndex++
        // }
        // 大-》小
        if (arr[i] > pivotVal) {
            swap(arr,i,startIndex)
            startIndex++
        }
    }
    swap(arr, startIndex, pivot)
    return startIndex
}

let arr = [100,32,434,5,6,7,1,23,1]
let arr1 = [85,231,1111,0,1,7,32,666,666777]
quickSort(arr,0,arr.length-1)
quickSort(arr1,0,arr1.length-1)
console.log(arr)
console.log(arr1)

// 简单版快排
function quickSort2 (arr) {
    if (arr.length < 1) return arr
    let left = [], right = [];
    const pivotVal = arr[0]
    for (let i = 1; i < arr.length;i++) {
        if (arr[i] >= pivotVal) {
            left.push(arr[i])
        }
        if (arr[i] < pivotVal) {
            right.push(arr[i])
        }
    }
    return [...quickSort2(left), pivotVal, ...quickSort2(right)]
}



var arr2 = [121,3434,23232,656,23232,121]
var arr3 = quickSort2(arr2)

console.log(arr3)

// 冒泡
function bubbleSort (arr) {
    if(!arr.length) return arr
    for (let i = 0; i < arr.length;i++) {
        let hasChange = false
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
                hasChange = true
            }
        }
        if (!hasChange) {
            break
        }
    }
    return arr
}

var arr4 = [5,435,65657,121,435,7776,98,0]
// 冒泡
console.log(bubbleSort(arr4))


// 
function insertSort (arr) {
    if (!arr.length) return arr
    for (let i = 1;i<arr.length;i++) {
        let temp = arr[i]
        let j = i-1
        for (j; j>=0;j--) {
            if (arr[j] > temp) {
                arr[j+1]=arr[j]
            } else {
                break
            }
        }
        arr[j+1] = temp
    }
    return arr
}

var arr5 = [5,435,65657,98,121,435,7776,98,0]
// 插入
console.log(insertSort(arr5))