线性排序：冒泡插入选择

思考：插入排序和冒泡排序的时间复杂度相同，都是 O(n2)，在实际的软件开发里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？

1 排序算法的执行效率

1.1 最好情况、最坏情况、平均情况时间复杂度

为什么要区分这三种时间复杂度呢？第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。

1.2 时间复杂度的系数、常数 、低阶

实际的软件开发中，我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

1.3 比较次数和交换（或移动）次数

这一节和下一节讲的都是基于比较的排序算法。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

2 排序算法的内存消耗

原地排序（Sorted in place）

3 排序算法的稳定性

经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。

4 冒泡排序（Bubble Sort）

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

实际上，刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。我这里还有另外一个例子，这里面给 6 个元素排序，只需要 4 次冒泡操作就可以了。

Array.prototype.bubbleSort = function () {
    for (let i = 0; i < this.length - 1; i++) {
        let flag = false
        for (let j = 0; j < this.length - 1 -i; j++) {
            if (this[j] > this[j + 1]) {
                const temp = this[j]
                this[j] = this[j + 1]
                this[j + 1] = temp
                flag = true
            }
        }
        if(!flag) break
    }
}
const arr = [5, 4, 3, 2, 1]
console.log(arr.bubbleSort(),arr);

三个问题总结：1.原地排序。2.稳定排序。3.复杂度

5 有序度

有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样：

有序元素对：a[i] <= a[j], 如果i < j。

关于这三个概念，我们还可以得到一个公式：逆序度 = 满有序度 - 有序度。我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。
对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是 0，所以要进行 n(n-1)/2 次交换。最好情况下，初始状态的有序度是 n(n-1)/2，就不需要进行交换。我们可以取个中间值 n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。

6 插入排序（Insertion Sort）

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

Array.prototype.insertionSort = function () {
    for (let i = 1; i < this.length; i++) {
        let temp = this[i]
        let j = i
        while (j>0) {
            if ( this[j - 1] > temp) {
                this[j] = this[j - 1]
            } else {
                break
            }
            j--
        }
        this[j] = temp
    }
}
const arr = [5, 4, 3, 2, 1]
arr.insertionSort()
console.log(arr)

原地，稳定，O(n) -> O(n2)

7 选择排序（Selection Sort）

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

Array.prototype.selectionSort = function () {
    for (let i = 0; i < this.length - 1; i++) {
        let minIndex = i;
        for (let j = i; j < this.length; j++) {
            if (this[j] < this[minIndex]) {
                minIndex = j
            }
        }
        let temp = this[i]
        this[i] = this[minIndex]
        this[minIndex] = temp
    }
}
const arr = [5, 4, 3, 2, 1]
arr.selectionSort()
console.log(arr)

原地，不稳定，O(n2)

8总结