专栏名称: 程序猿
本微信公众号:imkuqin,为程序员提供最新最全的编程学习资料的查询。目前已经开通PHP、C/C++函数库、.NET Framework类库、J2SE API查询功能。
目录
相关文章推荐
码农翻身  ·  今年后端这薪资是认真的吗? ·  16 小时前  
阿里云云栖号  ·  一周AI大事件 ·  昨天  
稀土掘金技术社区  ·  前端如何实现图片伪防盗链,保护页面图片 ·  昨天  
稀土掘金技术社区  ·  用dayjs解析时间戳,我被提了bug ·  2 天前  
玉伯  ·  企业家要 ego ... ·  2 天前  
51好读  ›  专栏  ›  程序猿

排序算法性能比较

程序猿  · 公众号  · 程序员  · 2016-11-15 17:17

正文

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


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






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