一、冒泡排序

冒泡排序的过程：从第一个元素开始，重复比较相邻的两个项，若第一项比第二项更大，则交换两者的位置；每一轮操作，都会将这一轮中最大的元素放置到数组的末尾。

编码实现：

/**
 * @description 冒泡排序
 * @param {*} arr
 * @return {*} 
 */
function bubbleSort(arr) {
    let len = arr.length
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
    return arr
}

思考①：

????????我们每一轮我们都将最大数放到了末尾，那我们还有必要在进行 len - 1?轮的判断吗？

????????答案当然是不用。为了避免这些冗余的比较动作，我们需要规避掉数组中的后 i 个元素。

编码实现：

/**
 * @description 冒泡排序优化
 * @param {*} arr
 * @return {*} 
 */
function betterbubbleSort(arr) {
    let len = arr.length
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
    return arr
}

思考②：

? ? ? ? 假设这个数组大部分都是有序的只有一小部分是无序的，那按我们上面的写法是不是有些判断就没有必要进行？

? ? ? ? 对的，最优的冒泡排序算法复杂度在最好情况下是 O(n)。

编码实现：

/**
 * @description 冒泡排序优化
 * @param {*} arr
 * @return {*} 
 */
function bestbubbleSort(arr) {
    let len = arr.length
    for (let i = 0; i < len; i++) {
        let flag = false
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
        // 若一次交换也没发生，则说明数组有序，直接放过
        if (!falg) return arr
    }
    return arr
}

时间复杂度：?平均复杂度?O(n^2)，最好复杂度 O(n)

二、选择排序

选择排序过程：循环遍历数组，每次都找出当前范围内的最小值，把它放在当前范围的头部；然后缩小排序范围，继续重复以上操作，直至数组完全有序为止。

编码实现：

/**
 * @description 选择排序
 * @param {*} arr
 * @return {*} 
 */
function selectSort(arr) {
    let len = arr.length
    for (let i = 0; i < len - 1; i++) {
        let index = i
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[index]) {
                index = j
            }
        }
        [arr[i], arr[index]] = [arr[index], arr[i]]
    }
    return arr
}

????????选择排序相对来说比较简单，它的思路导致了我们必须要走内层循环。

时间复杂度：?平均复杂度?O(n^2)

三、插入排序

插入排序过程：就是将当前元素前面的元素排序，然后进行插入。插入的意思就是将它放到前面合适的位置。（使用双指针来进行插入判断）

核心思想：找到元素在它前面那个序列中的正确位置

/**
 * @description 插入排序
 * @param {*} arr
 * @return {*}
 */
function insertSort(arr) {
    let len = arr.length
    for (let i = 1; i < len; i++) {
        let j = i;
        let temp = arr[i]
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1]
            j--
        }
        arr[j] = temp
    }
    return arr
}

时间复杂度：?平均复杂度?O(n^2)，最好复杂度?O(n)