排序（一）：冒泡排序、选择排序、插入排序

冒泡排序原理：
1.比较相邻元素，如果前一个元素比后一个元素大，就交换这两个元素的位置。
2.对每一对相邻的元素做同样的工作从开始第一对元素到结尾的最后一对元素，最终最后位置的元素就是最大
值。

冒泡.png

       let arr = [4, 3, 2, 1, 6, 5]
        //冒泡排序：O(n^2)
       for (let i = arr.length - 1; i > 0; i--) {
            for (let j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    let temp = arr[j]
                    arr[j] = arr[j + 1]
                    arr[j + 1] = temp
                }
            }
        }

选择排序原理：
1.每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处
的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引。
2.交换第一个索引处和最小值所在的索引处的值。

选择.png

        let arr1 = [4, 3, 2, 1, 6, 5, 9, 7]
        //选择排序:O(n^2)
        for (let i = 0; i < arr1.length - 1; i++) {
            let minIndex = i
            for (let j = i + 1; j < arr1.length; j++) {
                if (arr1[minIndex] > arr1[j]) {
                    minIndex = j
                }
            }
            let temp = arr1[i]
            arr1[i] = arr1[minIndex]
            arr1[minIndex] = temp
        }

插入排序原理：
1.把所有的元素分为两组，已经排序的和未排序的。
2.找到未排序的组中的第一个元素，向已经排序的组中进行插入。
3.倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位。

插入.png

        let arr2 = [4, 3, 2, 10, 12, 1, 5, 6]
        //插入排序：O(n^2)
        for (let i = 1; i < arr2.length; i++) {
            for (let j = i; j > 0; j--) {
                if (arr2[j - 1] > arr2[j]) {
                    let temp = arr2[j - 1]
                    arr2[j - 1] = arr2[j]
                    arr2[j] = temp
                } else {
                    break
                }
            }
        }

注：O(n^2)为时间复杂度。