注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

埖堓

 
 
 

日志

 
 
关于我

雨落风尽花红, 太匆匆, 路几重, 一夜春来秋去晚来风。 月色朦, 云雾胧, 清华过尽逍遥醉苍穹。 人生路, 视不同, 自是如水若空怎能懂? 江湖泪, 是与非, 爱恨情仇流去几个冬。

沈阳华威天下科技有限公司列出排序算法和性能的比较  

2017-03-03 10:34:52|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

所谓排序也就是将原来无序的一个序列重新排列成有序的序列。

排序方法中涉及到稳定性,所谓稳定性是指待排序的序列中有两个或两个以上相同的项,我们在排序前和排序后看这些相同项相对位置有没有发生变化,假如没有发生变化即该排序方法是稳定的,如果发生变化则说明该排序方法是不稳定的。

如果记录中关键字不能重复那么排序结果是唯一的,选择的排序方法稳定与否就无关紧要了;如果关键字可以重复则在选择排序方法时,就要根据具体的需求来考虑选择稳定还是不稳定的排序方法。那么哪些排序算法是不稳定的呢?

“快些选堆”:其中“快”指快速排序,“些”指希尔排序,“选”指选择排序“堆”指堆排序,即这四种排序方法是不稳定的其他自然都是稳定的。

排序算法分类

1、插入类排序

即在一个已经有序的序列中插入一个新的记录,就好比军训排队已经排好一个纵队,就在个时候来了个新家伙,于是新来的“插入”这个队伍中的合适位置。这类排序有:直接插入排序折半插入排序、希尔排序。

2、交换类排序

该类方法的核心是“交换”即每趟排序,都是通过一系列的“交换”动作完成的,如军训排队时教官说:你比旁边的高,你俩交换下还比下一个高就继续交换。这类排序有:冒泡排序、快速排序。

3、选择类排序

该方法的核心是“选择”即每趟排序都选出一个最小(或最大)的记录,把它和序列中的第一个(或最后一个)记录交换,这样最小(或最大)的记录到位。如军训排队时教官选出个子最小的同学,让他和第一个位置的同学交换剩下的继续选择。这类排序有:选择排序、堆排序。

4、归并类排序

所谓归并是将两个或两个以上的有序序列合并成一个新的有序序列。如军训排队时教官说:每个人先和旁边的人组成二人组组内排好队,二人组和旁边的二人组组成四人组,内部再排好队以此类推,直到最后全部同学都归并到一个组中并排好序。这类排序有:(二路)归并排序。

5、基数类排序

此类方法较为特别是基于多关键字排序的思想,把一个逻辑关键字拆分成多个关键字,如一副扑克牌按照基数排序思想可以先按花色排序,则分成4堆每堆再按A-K的顺序排序使得整副扑克牌最终有序。

排序算法分析

本文主要分析的排序算法有:冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序。

交换算法

由于大部分排序算法中使用到两个记录相互交换的动作,因此将交换动作单独封装出来便于各排序算法使用。

//交换函数

 Array.prototype.swap = function(i, j) {      

     var temp = this[i];      

     this[i] = this[j];      

     this[j] = temp;      

 }

插入排序

算法思想:每趟将一个待排序的关键字按照其关键字值的大小插入到已经排好的部分序列的适当位置上直到插入完成。

  //插入排序

  Array.prototype.insertionSort = function() {      

      for (var i = 1; i < this.length; ++i)      

      {      

          var j = i,

              value = this[i];      

          while (j > 0 && this[j - 1] > value)      

          {      

              this[j] = this[j - 1];      

             --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 < step; ++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;      

            }      

  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018