JavaScript 算法之数组排序之冒泡、插入

Question

冒泡排序

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(n*n)