冒泡排序，插入排序，希尔排序，快速排序

冒泡排序

function createArr(num) {
    let arr = new Array(num)
    for (let i = 0; i < num; i++) {
        arr[i] = Math.ceil(Math.random() * 10000);
    }
    return arr
}
function bubbleSort(arr) {
    console.time()
    let temp = 0 //临时存放元素的变量
    let flag = false //表示本次冒泡有无变换位置
    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]){
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                flag = true
            }
        }
        if (flag) {
            flag = false
        } else {
            break
        }
    }
    console.timeEnd()
      return arr
}
let targetArr = createArr(80000)
bubbleSort(targetArr)

插入排序

function createArr(num) {
    let arr = new Array(num)
    for (let i = 0; i < num; i++) {
        arr[i] = Math.ceil(Math.random() * 10000);
    }
    return arr
}
function insertSort(arr) {
    console.time()
    let val = 0  //存放有序数组的最后一个数,即要插入的数
    for (let i = 1; i < arr.length; i++) {
        val = arr[i]
        for (let j = i - 1; j > -1; j--) { //比当前数小，当前数往后移
            if (val < arr[j]) {
                arr[j + 1] = arr[j]
            }else {
                arr[j+1]=val //找到插入位置 跳出循环
                break
            }
            if(j===0&&val < arr[j]){ //到第一位，且插入数比第一位小，说明要插到第一位
                arr[j]=val
            }
        }
    }
    console.timeEnd()
       return arr
}
let targetArr = createArr(80000)
insertSort(targetArr)

希尔排序

function createArr(num) {
    let arr = new Array(num)
    for (let i = 0; i < num; i++) {
        arr[i] = Math.ceil(Math.random() * 10000);
    }
    return arr
}
function shellSort(arr) {
    console.time()
    let temp = 0
    for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < arr.length; i++) { //从第一组的第一个元素开始用插入法
            temp = arr[i]
            for (let j = i - gap; j > -1; j -= gap) { //按组遍历
                if (temp < arr[j]) {//比当前数小，当前数往后移
                    arr[j + gap] = arr[j]
                } else {
                    arr[j + gap] = temp//找到插入位置 跳出循环
                   break
                }
                if ((j-gap)<0 && temp < arr[j]) { //到第一位，且插入数比第一位小，说明要插到第一位
                    arr[j] = temp
                }
            }
        }
    }
    console.timeEnd()
    return arr
}
let targetArr = createArr(80000)
shellSort(targetArr)

快速排序

function createArr(num) {
    let arr = new Array(num)
    for (let i = 0; i < num; i++) {
        arr[i] = Math.ceil(Math.random() * 10000);
    }
    return arr
}
function quickSort(arr) {
    console.time()
    _quickSort(0, arr.length - 1)
    function _quickSort(left, right) {
        let l = left  //左下标 l的左边必须是小于pivor的元素
        let r = right  //右下标 r的右边必须是大于pivot的元素
        const pivotIndex = Math.floor((l + r) / 2)
        const pivot = arr[pivotIndex]  // 标准值
        let temp = 0 //辅助变量
        while (l < r) { //循环一遍  完毕的时候实现pivot左边都是比它小的数
            while (arr[l] < pivot) { //从左边开始找，跳出循环的时候说明找到了比pivot大的元素
                l++
            }
            while (arr[r] >= pivot) {  // 从右边开始找，跳出循环说明找到了比pivot小的元素
                r--
            }
            if (l > r) { //当条件成立，说明已经达成循环目标,相等时往下走，因为此时l要加1
                break
            }
            temp = arr[l]
            arr[l] = arr[r]
            arr[r] = temp
            r--
            l++
        }
        if (l === left && pivot === arr[pivotIndex]) { ///说明没有变化
            temp = arr[l]
            arr[l] = arr[pivotIndex]
            arr[pivotIndex] = temp
            l++
        }
        if (l < right) {// 右边部分超过两个需要排序
            _quickSort(l, right)
        }
        if (l > left + 1) { // 左边部分超过两个就需要排序
            _quickSort(left, l - 1)
        }
    }
    console.timeEnd()
    return arr
}
let arr = createArr(80000)
quickSort(arr)