|
我们开始讨论插入排序:直接插入排序是在已经有顺序的序列中,插入，然后再排序的过程. 时间复杂度:从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i＋2次（逆序）（i=1，2，…，n-1）。若分别用Cmin ，Cmax 和Cave表示元素的总比较次数的最小值、最大值和平均值，用Mmin ，Mmax 和Mave表示元素的总移动次数的最小值、最大值和平均值，则上述直接插入算法对应的这些量为： Cmin=n-1 Mmin=2（n-1） Cmax=1+2+…+n-1=（n^2-n）/2 Mmax=3+4+…+n+1=（n^2+3n-4）/2 Cave=（n^2+n-2）/4 Mmax=（n^2+7n-8）/4 因此，直接插入排序的时间复杂度为O(n^2) 空间情况:O(1) 只需要一个辅助空间 稳定性:稳定的算法 public class InsertSort { public void insertSort(int []array) { int len=array.length; //从第二个元素开始,应为第一个已经排好序了 12,1,5,3 for(int i=1;i<len;i++) { //找到比array更加小的值 int j=0; while(j<=i && array>array[j]) { j++; } if(j<i)//j<i的时候才移动i前面的数据 { //记录array的值 int temp=array; for(int k=i-1;k>=j;k--)//移动i之前的数据 { array[k+1]=array[k]; } //j的位置值为插入的新值 array[j]=temp; } } } public void disp(int[] array) { for(int i=0;i<array.length;i++) { System.out.println(array); } } public static void main(String[] args) { int[] array=new int[]{2,7,6,1,4}; InsertSort sort=new InsertSort(); sort.insertSort(array); sort.disp(array); } } |
行业聚焦 面试交流 职位推荐 开发视频 技术交流 腾讯微博 新浪微博
友情链接：课课家教育 阿里云 鲜果 W3Cfuns前端网 中国企业家 环球企业家 投资界 传媒梦工场 MSN中文网 Android开发者社区 cnbeta 投资中国网 又拍云存储 美通说传播 IT茶馆 网商在线 商业评论网 TechOrange IT时代周刊 3W创新传媒 开源中国社区 二维工坊 Iconfans 推酷 智能电视网 FreeBuf黑客与极客 财经网 DoNews 凤凰财经 新财富 eoe移动开发者社区 i黑马 网易科技 新浪科技 搜狐IT 创业家 创业邦 腾讯财经 福布斯中文网 天下网商 TechWeb 雷锋网 新浪创业 和讯科技 品途O2O 极客公园 艾瑞网 抽屉新热榜 卖家网 人民网通信频道 拉勾网 创新派 简单云主机
手机版|黑名单|守望者 成才网 在线教育 linux 高级程序设计 C/C++ 大数据
( 蜀ICP备14029946号 ) 
成都守望者科技有限公司 © 2013-2016 All Rights Reserved
收藏