正文
];
--j;
}
this
[j] = value;
}
}
算法性能:
在内层循环中this[j]=this[j-1],这句是作为基本操作。考虑最坏情况,即整个序列是逆序的,则其基本操作总的执行次数为n*(n-1)/2,其时间复杂度为O(n*n)。考虑最好情况,即整个序列已经有序,则循环内的操作均为常量级,其时间复杂度为O(n)。因此本算法平均时间复杂度为O(n*n)。算法所需的额外空间只有一个value,因此空间复杂度为O(1)。
希尔排序
算法思想:希尔排序又叫做缩小增量排序,是将待排序的序列按某种规则分成几个子序列,分别对这几个子序列进行插入排序,其中这一规则就是增量。如可以使用增量5、3、1来分格序列,且每一趟希尔排序的增量都是逐渐缩小的,希尔排序的每趟排序都会使得整个序列变得更加有序,等整个序列基本有序了,再使用一趟插入排序,这样会更有效率,这就是希尔排序的思想。
Array.prototype.shellSort = function() {
for (var step = this.length >> 1; step > 0; step >>= 1)
{
for (var i = 0; i for (var j = i + step; j this.length; j += step)
{
var k = j, value = this[j];
while (k >= step && this[k - step] > value)
{
this[k] = this[k - step];
k -= step;
}
this[k] = value;
}
}
}
}
算法性能:
希尔排序的时间复杂度平均情况为O(nlogn),空间复杂度为O(1)。希尔排序的增量取法要注意,首先增量序列的最后一个值一定是1,其次增量序列中的值没有除1之外的公因子,如8,4,2,1这样的序列就不要取(有公因子2)。
冒泡排序
算法思想:通过一系列的“交换”动作完成的,首先第一个记录与第二个记录比较,如果第一个大,则二者交换,否则不交换;然后第二个记录和第三个记录比较,如果第二个大,则二者交换,否则不交换,以此类推,最终最大的那个记录被交换到了最后,一趟冒泡排序完成。在这个过程中,大的记录就像一块石头一样沉底,小的记录逐渐向上浮动。冒泡排序算法结束的条件是一趟排序没有发生元素交换。
Array.prototype.bubbleSort = function() {
for (var i = this.length - 1; i > 0; --i)
{
for (var j = 0; j if (this[j] > this[j + 1])
this.swap(j, j + 1);
}
}
算法性能:最内层循环的元素交换操作是算法的基本操作。最坏情况,待排序列逆序,则基本操作的总执行次数为(n-1+1)*(n-1)/2=n(n-1)/2,其时间复杂度为O(n*n);最好情况,待排序列有序,则时间复杂度为O(n),因此平均情况下的时间复杂度为O(n*n)。算法的额外辅助空间只有一个用于交换的temp,所以空间复杂度为O(1)。
快速排序
算法思想:以军训排队为例,教官说以第一个同学为中心,比他矮的站他左边,比他高的站他右边,这就是一趟快速排序。因此,一趟快速排序是以一个枢轴,将序列分成两部分,枢轴的一边比它小(或小于等于),另一边比它大(或大于等于)。
Array.prototype.quickSort = function(s, e) {
if (s == null)
s = 0;
if (e == null)
e = this.length - 1;
if (s >= e)
return;
this.swap((s + e) >> 1