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

Mr. almost

Never mind,live goes on.On my way again.

 
 
 

日志

 
 

插入排序回顾  

2010-04-02 23:47:15|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
使用范围:小规模数据的排序的最佳方案,而且是一种稳定的排序。
  算法复杂度:O(n2)
  思想:
  首先我们来想一个问题,我们是否能找到一种方法,使一个数插入到一个有序的数组当中,并保证它依然有序呢?
  那么,我们又如何将一组无序的数插入到一个有序的数组之中,并且保证它依然有序呢?
 
  至此,聪明的读者就会发现,解决了这两个问题,我们就知道如何排序了。
 
  下面我们来详细的讲解一下查入排序的思想: 

  首先我们将一组无序的数分为两组,一组有序的,记作A,一组无序的,记作B。开始的时候A中只有一个元素,显然只有一个元素的数组是有序的,我们开始将B中的元素逐个插入到A中,并且每一次插入都保证A是有序的,一直将B中的元素全部插入到A中,那么我们就将这个数组排好序了。 

  下面我们来看一下如何将一个数插入到一个有序数组中,有一个数组{3,5,7,9,12}和一个数6,我们可以从数组的前面开始查找直到找到一个不小于6的数,然后把6放在他前面。我们也可以从数组的后面开始查找直到找到一个不大于6的数,然后把6放到他的后面。或者我们可以用二分查找到6应该在数组中的位置然后把6放在那。在这个查找位置的过程中,基于比较的复杂度依次是O(n)、O(n)、O(log2n)。 

  那么,将一个数组排序的过程,就是将有序数组不断增大的过程,从开始只有一个元素,到后来整个数组都是有序的,那么,每插入一次的时间复杂度与有序数组的大小有关,假设目前的有序数组大小为i,此次插入的最坏比较次数为i,那么,最坏情况下,也就是数组倒序时,总体的比较次数为1+2+3+…+(n-1)=n(n-1)/2 

  最好情况下,也就是数组有序时,这时的比较次数为n-1次。 

  平均情况下,一次插入的比较次数为i/2,总体的比较次数为1/2+2/2+3/2+…+(n-1)/2=n(n-1)/4 

  所以,平均情况下比较复杂度为O(n2),如果我们考虑每次插入,在查找位置时使用二分查找,平均情况下比较复杂度为O(nlog2n)。 

  细心的读者会发现,插入排序的时间复杂度不是O(n2)吗?怎么变成O(nlog2n)了?其实,在排序的过程中,除了比较的花销之外,还有元素移动的花销。 

  如果用数组来实现,每次移动的花销是O(n),总体的花销是O(n2)。
  如果用链表来实现,每次移动的花销是O(1),但查找时就不能用二分法,所以总体的花销还是O(n2)。
  下面给出一个用数组为数据结构的插入排序的C++代码:
  /**
  * 插入排序方法
  * @param array 数组名
  * @param left 排序的起始位置
  * @param length 数组要排序的长度
  * @author oracleot & Iceer
  */
  void insertSort(int * array, int left, int length) {
  //对一开始的数组,可分为[left,left+1)有序数组,考试,大提示只有一个数
  //[left+1,left+length)无序数组。
  for( int i = left + 1; i < left + length ; ++ i ) {
  //现在的任务是把array[i]插入到array[left,i)中。
  int current = array[i] ;
  int j ;
  //如果current不小于array[j]则把current查入到j+1位置。()
  for( j = i-1; (j >= left) && (current < array[j]); -- j ) {
  array[j+1] = array[j] ;
  }
  array[j+1] = current ;
  }
  }
  评论这张
 
阅读(146)| 评论(0)
推荐

历史上的今天

评论

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

页脚

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