By

文章目录

冒泡排序

Array.prototype.bubble_sort = function() {
    var i, j, temp;
    for (i = 0; i < this.length - 1; i++)
        for (j = 0; j < this.length - 1 - i; j++)
            if (this[j] > this[j + 1]) {
                temp = this[j];
                this[j] = this[j + 1];
                this[j + 1] = temp;
            }
    return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.bubble_sort();

冒泡排序顾名思义就是一个个气泡不断往上浮动的意思。在JS的这段代码中就是不断将最大的数字排在数组尾部，然后类似数学归纳法一般，用同样的方式处理接下来的n-1个数字。这种算法需要计算(n-1)+(n-2)+…+1=(n-1)n/2次，达到O(nn)的级别。

插入排序

Array.prototype.insertion_sort = function() {
    var i, j;
    var temp;
    for (i = 1; i < this.length; i++) {
        temp = this[i];
        for (j = i - 1; j >= 0 && this[j] > temp; j–)
            this[j + 1] = this[j];
        this[j + 1] = temp;
    }
    return this;
};


插入排序对同样的数组进行排序就会表现的好一点，它的原理是在已经排序完成的数组基础上添加新数，从后往前进行比较并插入正确的位置。这种排序方式在最优的情况只需要计算n-1次(即原来的数列已经排序完成),在最差的情况需要计算1+2+…+(n-1)=n(n-1)/2次，即平均复杂度为O(nn)

文章目录