冒泡排序

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)