SOURCE

window.onload = function() {
    const arr = [3,5,2,9,10,19,13,6,4,7]
    // 冒泡排序 稳定
    // 不断的对相同的两组数进行比较，选择较大或较小的一个替换
    // 没循环一遍次数都会减少一次
    console.time('冒泡耗时')
    function maopao(arr) {
        let len = arr.length
        for(let i = 0; i < len; i++) {
            for (let j = 0; j < len - i; j++) {
                if (arr[j] > arr[j+1]) {
                    let tmp = arr[j]
                    arr[j] = arr[j+1]
                    arr[j+1] = tmp
                }
            }
        }
        return arr
    }
    
    console.log('冒泡排序',maopao(arr))
    console.timeEnd('冒泡耗时')
    // 选择排序 不稳定
    // 每次选择一个最大值或最小值放到最后面或最前面
    function xuanze(arr) {
        let len = arr.length
        let minIndex
        let result = []
        for(let i = 0; i < len; i++) {
            // 每次设置一个最小值为遍历数组元素的第一个值
            minIndex = i
            for(let j = i; j < len; j++) {
                // 其他数组值不断的之比较然后重新设置最小值
                if (arr[j] < arr[minIndex]) {
                    minIndex = j
                }
            }
            // 最小值与第一位交换
            let tmp = arr[i]
            arr[i] = arr[minIndex]
            arr[minIndex] = tmp
        }
        return arr
    }
    console.log('选择排序', xuanze(arr))
    // 插入排序：稳定
    // 从数组第二项开始，不断的拿出数组与之前的相比较，如果小于就交换位置
    function charu(arr){
        let len = arr.length
        for(let i = 0; i < len; i++) {
            for (let j = 0; j < i; j++) {
                if (arr[j] < arr[j-1]) {
                    let tmp = arr[j-1]
                    arr[j-1] = arr[j]
                    arr[j] = tmp
                }
            }
        }
        return arr
    }
    console.log('插入排序', charu(arr))
    // 快速排序 不稳定
    // 在数组中选择一个中间值作为基准点，然后定义两个空数组，分为左和右
    // 把原始数组和基准点做比较，小的值放在左边，大的值放在右边，然后在对左右数组进行同样的操作
    // 进行不断递归需要有点临界点判断，当数组长度为1时，不用判断了 直接返回
    function kuaisu(arr) {
        if (arr.length <= 1) return arr
        // 去基准点
        let pointIndex = arr.splice(Math.floor(arr.length / 2), 1)[0]
        let len = arr.length
        let left = []
        let right = []
        // 取出基准点的数组元素
        
        for (let i = 0; i < len; i++) {
            if (arr[i] < pointIndex) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }
        return kuaisu(left).concat([pointIndex],kuaisu(right))
    }
    console.log('快速排序', kuaisu(arr))
    // 归并排序 稳定 采用分而治之的，至上而下的的递归调用方式，把数组不断的进行拆分，然后比价两个数组的第一项
    // 小的放入左数组，大的放入又数组，不断的递归，主要需要有个临街条件
    function merge(arr) {
     if (arr.length < 2) return arr
     let middle = Math.floor(arr.length/2)
     let left = arr.slice(0, middle)
     let right = arr.slice(middle)
     return guibing(merge(left), merge(right))
    }
    function guibing(left, right) {
        let result = []
        while(left.length && right.length) {
            if (left[0] <= right[0]) {
                result.push(left.shift())
            } else {
                result.push(right.shift())
            }
        }
        while(left.length) {
            result.push(left.shift())
        }
        while(right.length) {
            result.push(right.shift())
        }
        return result
    }
    console.log('归并排序', merge(arr))
    // 希尔排序 不稳定
    // 采用对数组进行间隔处理，通过一定的间隔gap对数组数组分组，然后对每组进行插入排序，每次遍历完毕之后
    // 在对数组进行gap/2进行处理，重复循环，知道gap<=1 时停止，最后对排序的数组进行插入排序，这样在时间
    // 的效率上会加快
    function shellSort(arr) {
        for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
        // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
        for(let i = gap; i < arr.length; i++) {
            let j = i;
            let temp = arr[j];
            for(; j> 0; j -= gap) {
                if(temp >= arr[j-gap] || j - gap < 0) {
                    break;
                }
                arr[j] = arr[j-gap];
            }
            arr[j] = temp;
        }
    }
    return arr;
    }
    console.log('希尔排序', shellSort(arr))
}