Javascript 基本排序算法（冒泡排序、选择排序、插入排序

冒泡排序

之所以叫冒泡排序的原因是，数据值会像气泡一样从数组的一端漂浮到另一端。
假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将他们进行互换

特点：外层循环每次找出最大值 内层循环遍历每次减少循环的次数。

Array.prototype.bubbleSort = function() {
    for (let i = 0; i < this.length; i++) {
        for (let j = 0; j < this.length - 1 - i; j++) {
            if (this[j] > this[j + 1]) {
                let temp = this[j]
                this[j] = this[j + 1]
                this[j + 1] = temp
            }
        }
    }
    return this
}

// 测试代码
console.log([5, 4, 3, 2, 1].bubbleSort())

选择排序

选择排序是从数组的开头开始，将第一个元素和其他元素进行比较，检查完所有的元素后，将最小的元素放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个元素时，所有的元素便完成了排序。

特点：外层循环从数组的第一个元素移动到数组的第二个元素；内循环从第一个数组元素移动到最后一个元素；

内层循环寻找最小值的位置,且内层循环的遍历从i开始, 因为每次都少遍历一个元素，适用于求最小值。

Array.prototype.selectionSort = function() {
    for(let i = 0; i < this.length -1; i++) {
        let indexMin = i; 

        for(var j = i; j < this.length; j++) {
            if(this[indexMin] > this[j]) {
                indexMin = j
            }
        }

        if(i != indexMin) { 
            let temp = this[i]
            this[i] = this[indexMin]
            this[indexMin] = temp 
        }
    }
    
    return this
}

// 测试代码
console.log([5, 4, 3, 2, 1].selectionSort())

插入排序

依次选择元素，插入到合适的位置。

特点：从第二个元素开始插入，外循环将数据元素挨个移动，而内循环则对外循环中选中的元素及它前面的那些元素进行比较。如果外循环中选中的元素比内循环中的元素小，那么数据元素会向右移动，为内循环中的这个元素腾出位置。

这种方法是常见的写法。

Array.prototype.insertionSort = function () {
    let j 
    let temp 

    for(let i = 1; i < this.length; i++) {
        j = i // 位置
        temp = this[i] // 当前值

        while(j > 0 && this[j - 1] > temp) {
            this[j] = this[j -1]
            j--
        }

        this[j] = temp 
        console.log(this.join(', '))
    }
    return this
}

改写插入排序

将while循环改写为for循环

外层循环挨个移动元素，内循环对外循环选中的元素以及它前面的哪些元素进行比较，如果外循环中选中的元素比内循环中选中的元素小，那么数据元素会向右移动。

Array.prototype.insertionSort (arr) {
    for(let i = 1; i < arr.length; i++) {
        let temp = arr[i]
        let tempIndex = i; 

        for(let j = i; j > 0; j--) {
            if(arr[j - 1] < temp) {
                break;
            }
            arr[i] = arr[j - 1]
            tempIndex = j -1;
        }
        arr[tempIndex] = temp;
    }
    return arr
}

console.log([2, 7, 0, 2, 45, 12].insertionSort())

这三种排序算法中，选择排序和插入排序要不冒泡排序快，插入排序是这三种算法中最快的。