1、冒泡排序

思路：（1）第一次找出最大的数放在最后一个位置, 需要两个数据项进行比较，是一个循环操作。（2） 第二次将第二大的数倒数第二个位置，也是两个数据项进行比较，只是不和最后一个数据项比较(少了一次)， 但是也是一个循环操作 。（3） 第三次...第四次...依次类推。（4） 其中规律就是一个循环中嵌套循环，并且被嵌套的循环次数越来越少的。

function maoSort(arr) {

    var length = arr.length

    for (var i = 1; i < length; i++) {

        for (var j = 0; j < length - i; j++) {

            if (arr[j] > arr[j+1]) {

                var temp = arr[j+1]

                arr[j+1] = arr[j]

                arr[j] = temp

            }

        }

    }

    return arr

}

比较次数，。

交换平均次数,

2、选择排序

改进了冒泡排序，（1）将交换次数由减少到了。（2）比较次数扔是。

思路：（1）选择第一个索引的位置，与后面元素依次比较，经过一轮的比较，记录最小的索引值，将最小的值与第一个位置交换。（2）第二轮会记录第二小的数，将第二小的值与第二个位置交换。第三轮会记录第三小的数，将第三小的值与第三个位置交换。。。依次类推。直到n-1轮。

function selectionSort(arr) {

    var length = arr.length

    for (var i = 0; i < length - 1; i++) {  // 外层循环: 从0位置开始取出数据, 直到length-2位置

        var min = i

        for (var j = min + 1; j < length; j++) {  // 内层循环: 从i+1位置开始, 和后面的内容比较

            // .如果i位置的数据大于j位置的数据, 那么记录最小的位置

            if (arr[i] > arr[j]) min = j

        }

        var temp = arr[i]

        arr[i] = arr[min]

        arr[min] = temp

    }

    return arr

}

3、插入排序

思路：（1）从第一个元素开始，该元素可被认为已经排好序。（2）取出下一个元素，在已经排序的元素序列中从后往前扫描，扫描时如果该元素大于已排序的元素，交换两者位置。（3）重复步骤2，直到该元素大于等于已排序的元素。（4）将该元素插入到该位置后，重复上述步骤来插入后续元素。

function insertionSort(arr) {

    var length = arr.length

    //  外层循环: 外层循环是从1位置开始, 依次遍历到最后

    for (var i = 1; i < length; i++) {

        // 记录选出的元素, 放在变量temp中

        var temp = arr[i]

        var j = i

        //内层循环不确定循环的次数, 最好使用while循环

        while (arr[j - 1] > temp && j > 0) {

            arr[j] = arr[j - 1]

            j--

        }

        //  将选出的j位置, 放入temp元素

        arr[j] = temp

    }

    return arr

}

比较次数：第一趟最多1次，第二趟最多2次....第n趟最多N-1次，最多的比较次数：，平均比较次数.

复制次数：第一趟最多1次，第二趟最多2次....第n趟最多N-1次，最多的比较次数：，平均复制次数。

4、希尔排序

希尔排序建立在插入排序的基础上。

function shellSort(arr) {

    var length = arr.length

    var gap = length >> 1

    // 增量不断变量小, 大于0就继续排序

    while (gap >= 1) {

        // 4.实现插入排序

        for (var i = gap; i < length; i++) {

            // 4.1.保存临时变量

            var temp = arr[i]

            var j = i

            // 4.2.插入排序的内层循环

            while (arr[j - gap] > temp && j > gap - 1) {

                arr[j] = arr[j - gap]//复制.

                j -= gap

            }

            // 4.3.将选出的j位置设置为temp

            arr[j] = temp

        }

        gap = gap >> 1

    }

}

希尔排序的平均时间复杂度为o(nlogn)。

5、快速排序

思路：分而治之。平均效率：o(nlogn)

function quickSort(arr){

    if(arr.length === 0){

        return []

    }

    let midIndex = arr.length >> 1

    let mid = num.splice(midIndex, 1)

    let left = []

    let right = []

    for(let i = 0; i < arr.length; i++){

        if(num[i] < mid){

            left.push(num[i])

        }else{

            right.push(num[i])

        }

    }

    arr = quickSort(left).contact(mid, quickSort(right))

    return arr

}