插入排序算法

2015-08-14 21:24 阅读 3,159 次 评论 0 条
版权声明:本文著作权归TeachCourse所有,未经许可禁止转载,谢谢支持!
转载请注明出处:http://teachcourse.cn/330.html

一.摘要

什么叫做插入排序算法?在一组排序好的数组中插入当前值,找到插入的合适位置。很喜欢用来比喻的一个例子:咋俩一起打扑克牌,我左手拿着排序好的牌,右手将摸到的牌放到左手中,找到合适的位置保证插入后是有序的。

二.作用

Java或android开发中最简单的排序算法,适合对少量元素进行快速排序,不需要额外的存储空间,最坏的运行时间是O(n2),通常对数组进行排序或其他操作可以参考《Arrays方法解析》。

三.封装

插入排序算法根据排序的特点,选定一个position位置,确定当前值currentValue,然后让当前值与左边每个值比较,左边的值大于currentValue则彼此交换位置,继续一轮的比较,知道插入排序完成,代码如下:

第一种写法:

  1. public void insertSort(int[] array){  
  2.       if (array == null || array.length < 2) {    
  3.             return;    
  4.         }   
  5.       for (int i = 1; i < array.length; i++) {   
  6.             int position = i; //记录当前位置  
  7.             int currentValue = array[i];  //获取当前值  
  8.   
  9.         //当前值与左边每个值比较,交换位置  
  10.             for (int j = i - 1; j >= 0; j--) {  
  11.                 if (array[j] > currentValue) {    
  12.                     array[j + 1] = array[j];    
  13.                     position -= 1;    
  14.                 } else {    
  15.                     break;    
  16.                 }   
  17.   
  18.         array[position] = currentValue;  
  19.       }    
  20.                
  21. }  

第二种写法:

  1. public void insertSort(int a[]){    
  2.         int length=a.length; //数组长度    
  3.         int j;               //当前值的位置    
  4.         int i;               //指向j前的位置    
  5.         int key;             //当前要进行插入排序的值    
  6.         //从数组的第二个位置开始遍历值    
  7.         for(j=1;j<length;j++){    
  8.             key=a[j];    
  9.             i=j-1;    
  10.             //a[i]比当前值大时,a[i]后移一位,空出i的位置,好让下一次循环的值后移    
  11.             while(i>=0 && a[i]>key){    
  12.                 a[i+1]=a[i]; //将a[i]值后移    
  13.                 i--;         //i前移    
  14.             }//跳出循环(找到要插入的中间位置或已遍历到0下标)    
  15.             a[i+1]=key;    //将当前值插入    
  16.         }    
  17.     }    
关注公众号 扫一扫二维码,加我QQ

如果文章对你有帮助,欢迎点击上方按钮关注作者

来源:TeachCourse每周一次,深入学习Android教程,关注(QQ1589359239或公众号TeachCourse)
转载请注明出处:http://teachcourse.cn/330.html
分类:数据结构 标签:,
怎么快速进行Android开发的几个总结 怎么快速进行Android开发的几个
Android开发之深入理解工厂(Factory)模式 Android开发之深入理解工厂(F
关于WordPress后台设置中的WordPress地址和站点地址的解读 关于WordPress后台设置中的Wo
面向抽象的编程思想 面向抽象的编程思想

发表评论

呲牙 憨笑 坏笑 偷笑 色 微笑 抓狂 睡觉 酷 流汗 鼓掌 大哭 可怜 疑问 晕 惊讶 得意 尴尬 发怒 奋斗 衰 骷髅 啤酒 吃饭 礼物 强 弱 握手 OK NO 勾引 拳头 差劲 爱你

表情