首页 > 代码库 > 《算法导论》习题2.3-6 改进的InsertSort
《算法导论》习题2.3-6 改进的InsertSort
InsertSort中有关键的一步是把当前元素A[i]插入到已经排好序的A[1，i-1]的合适的位置上，在原始的InsertSort算法中，
采用的是从后往前一步一步查找的方法，习题2.3-6要求利用习题2.3-5中的binary search的方法，加速这个插入的过程。
把binary search 的算法稍加修改，就可以返回正确的，插入元素的位置：
public static int findInsertPlace(int [] A,int target,int a, int b) { int middle = a+(b-a)/2; if(a>b) return a; else if (A[middle]==target) return middle; else if (A[middle]< target) return findInsertPlace(A,target,middle+1,b); else return findInsertPlace(A,target,a,middle-1); }
findInsertPlace和binary search唯一的不同，在于：
if(a>b) return a;
同学们可以动手画一画，检验一下到底对还是不对。
改进后的InsertSort如下：
public class ImprovedInsertSort { public static void sort(int [] A) { for(int i =1; i<A.length;i++) { int temp = A[i]; int insertPlace = findInsertPlace(A,temp,0,i-1); for(int j= i-1 ; j>=insertPlace; j--) A[j+1] =A[j]; A[insertPlace] = temp; } return ; } public static int findInsertPlace(int [] A,int target,int a, int b) { int middle = a+(b-a)/2; if(a>b) return a; else if (A[middle]==target) return middle; else if (A[middle]< target) return findInsertPlace(A,target,middle+1,b); else return findInsertPlace(A,target,a,middle-1); } public static void main(String[] args) { // TODO Auto-generated method stub int A [] ={1, 7,5,5 ,2, 4,6, 7,4,23,11,34,15}; ImprovedInsertSort.sort(A); for(int a:A) System.out.print(a+" "); }}
改进之前，InsertSort在最坏情况下是O(n^2)，改进之后，是O( n*lg(n) )，算法效率大大提升了。
《算法导论》习题2.3-6 改进的InsertSort
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。