排序算法性能比较

正文

请到「今天看啥」查看全文

];                   --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

请到「今天看啥」查看全文