SOURCE

let arr = []
for(let i = 0; i < 10; i++) {
    arr.push(Math.floor(Math.random() * 10))
}
console.log(arr)
// bubbleSort(arr)
// insetSort(arr)
// console.log(mergeSort(arr))
// changeSort(arr)
// shellSort(arr)
console.log(quickSort(arr))

//冒泡排序
function bubbleSort(arr) {
    for(let i = 0; i < arr.length - 1; i++) {
        for(let j = 0; j < arr.length - 1 - i; j++) {
            if(arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(arr)
}

//插入排序
function insetSort(arr) {
    for(let i = 1; i < arr.length; i++) {
        let index = i;
        let temp = arr[i];
        while(index > 0 && arr[index - 1] > temp) {
            index--;
        }
        arr.splice(i, 1);
        arr.splice(index, 0, temp);
    }
    console.log(arr)
}

//归并排序
function mergeSort(arr) {
    if(arr.length < 2) {
        return arr
    }
    let mid = Math.floor(arr.length / 2);
    let leftArr = arr.slice(0, mid);
    let rightArr = arr.slice(mid);
    return merge(mergeSort(leftArr), mergeSort(rightArr))
}
function merge(leftArr, rightArr) {
    let res = [];
    while(leftArr.length > 0 && rightArr.length > 0) {
        if(leftArr[0] < rightArr[0]) {
            res.push(leftArr.shift())
        }else {
            res.push(rightArr.shift())
        }
    }
    if(leftArr.length != 0) {
        res.push(...leftArr)
    }
    if(rightArr.length != 0) {
        res.push(...rightArr)
    }
    return res
}

//选择排序
function changeSort(arr) {
    for(let i = 0; i < arr.length - 1; i++) {
        let index = i;
        for(let j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[index]) {
                index = j;
            }
        }
        let temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
    console.log(arr)
}

//希尔排序
function shellSort(arr) {
    for(let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for(let i = gap; i < arr.length; i ++) {
            let index = i;
            let temp = arr[i];
            while(index > 0 && arr[index - gap] > temp) {
                index -=gap;
            }
            arr.splice(i, 1);
            arr.splice(index, 0, temp);
        }
    }
    console.log(arr)
}

//快速排序
function quickSort(arr) {
    if(arr.length < 2) {
        return arr
    }
    let index = Math.floor(arr.length / 2);
    let temp = arr.splice(index, 1)[0];
    let leftArr = [];
    let rightArr = [];
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < temp) {
            leftArr.push(arr[i]);
        }else {
            rightArr.push(arr[i]);
        }
    }
    return [...quickSort(leftArr), temp, ...quickSort(rightArr)]
}