学步园

折半插入排序算法基本思想：
折半插入排序算法是对直接插入排序算法的一种改进。在直接插入排序算法中，向有序序列中插入一个元素，插入位置是把待插入元素关键字与有序序列中元素的关键字逐个比较得到的。

折半插入排序算法的基本思想是：
 向有序序列中插入元素，那么插入位置可以不断地平分有序序列，并把待插入的元素的关键字与平分有序序列的关键字比较，以确定下一步要平分的子序列，直到找到合适的插入位置位置。

注意先分析好折半插入排序的算法，然后再看代码：

package org.pbdevj.ds.sort.insert;</p> <p>/**折半[二分法]插入排序*/<br /> public class BinaryInsertSort implements ISort {</p> <p> private Element[] elements;</p> <p> public BinaryInsertSort() {<br /> // TODO Auto-generated constructor stub<br /> }</p> <p> public BinaryInsertSort(Element[] elements) {<br /> // TODO Auto-generated constructor stub<br /> this.elements = elements;<br /> }</p> <p> @Override<br /> public void output() {<br /> // TODO Auto-generated method stub<br /> // TODO Auto-generated method stub<br /> if (elements!=null){<br /> for (Element e : elements) {<br /> System.out.println(e);<br /> }<br /> }<br /> }</p> <p> @Override<br /> public void sort() {<br /> // TODO Auto-generated method stub<br /> if (elements==null || elements.length==0 || elements.length==1)<br /> return;<br /> //数组:2 9 5 3 2 1 10<br /> //下标:0 1 2 3 4 5 6<br /> for (int i = 1; i < elements.length; i++) {//整个循环都是为了找插入位置<br /> int start = 0;<br /> int end = i;<br /> int mid = 0;<br /> while(start<end){<br /> //折半<br /> mid = (start+end)/2;<br /> //分三种情况讨论<br /> //情况一:折半后的中间位置元素恰好等于当前元素<br /> if (elements[mid].compareTo(elements[i])==0){<br /> end = mid;<br /> break;<br /> }<br /> //情况二:折半后的中间位置元素小于当前元素<br /> if (elements[mid].compareTo(elements[i])<0){<br /> start=mid+1;//修改搜索的起始下标继续搜索<br /> continue;<br /> }<br /> //情况三:折半后的中间位置元素大于当前元素<br /> if (elements[mid].compareTo(elements[i])>0){<br /> end = mid;<br /> }<br /> }</p> <p> //end就是要插入的位置<br /> insertItem(elements,end,i);<br /> }<br /> }</p> <p> @Override<br /> public void sort(ISortCallBack sortCallBack) {<br /> // TODO Auto-generated method stub<br /> if (elements==null || elements.length==0 || elements.length==1)<br /> return;<br /> //数组:2 9 5 3 2 1 10<br /> //下标:0 1 2 3 4 5 6<br /> for (int i = 1; i < elements.length; i++) {//整个循环都是为了找插入位置<br /> if (sortCallBack!=null)<br /> sortCallBack.visit(elements[i]);</p> <p> int start = 0;<br /> int end = i;<br /> int mid = 0;<br /> while(start<end){<br /> //折半<br /> mid = (start+end)/2;<br /> //分三种情况讨论<br /> //情况一:折半后的中间位置元素恰好等于当前元素<br /> if (elements[mid].compareTo(elements[i])==0){<br /> end = mid;<br /> break;<br /> }<br /> //情况二:折半后的中间位置元素小于当前元素<br /> if (elements[mid].compareTo(elements[i])<0){<br /> start=mid+1;//修改搜索的起始下标继续搜索<br /> continue;<br /> }<br /> //情况三:折半后的中间位置元素大于当前元素<br /> if (elements[mid].compareTo(elements[i])>0){<br /> end = mid;<br /> }<br /> }</p> <p> //end就是要插入的位置<br /> insertItem(elements,end,i);<br /> }<br /> }</p> <p> /**<br /> *<br /> * 将indexSrc元素插入到elements中的indexTarget位置,indexTarget位置之后的数向后移一位<br /> * indexSrc应该大于indexTarget<br /> * */<br /> private void insertItem(Element[] elements,int indexTarget,int indexSrc){<br /> if (elements==null ||<br /> elements.length<=1 ||<br /> indexTarget<0 ||<br /> indexTarget>elements.length ||<br /> indexSrc<0 ||<br /> indexSrc>elements.length ||<br /> indexSrc==indexTarget){<br /> return;<br /> }<br /> Element e = elements[indexSrc];//记录下带插入的元素<br /> for (int i = indexSrc; i > indexTarget; i--) {//插入位置后的元素依次后移<br /> elements[i] = elements[i-1];<br /> }<br /> elements[indexTarget] = e;//插入这个元素<br /> }</p> <p>}<br />

测试代码：

package org.pbdevj.ds.sort.insert.utest;</p> <p>import org.pbdevj.ds.sort.insert.BinaryInsertSort;<br /> import org.pbdevj.ds.sort.insert.Element;<br /> import org.pbdevj.ds.sort.insert.ISort;<br /> import org.pbdevj.ds.sort.insert.ISortCallBack;<br /> import org.pbdevj.ds.sort.insert.InsertSort;</p> <p>public class BinaryInsertSortTest {</p> <p> /**<br /> * @param args<br /> */<br /> public static void main(String[] args) {<br /> // TODO Auto-generated method stub<br /> Element[] elements=new Element[]{<br /> new Element(90),<br /> new Element(60),<br /> new Element(70),<br /> new Element(60),<br /> new Element(70),<br /> new Element(40),<br /> new Element(90),<br /> new Element(10)<br /> };<br /> ISort sort = new BinaryInsertSort(elements);<br /> System.out.println("before sort....");<br /> sort.output();<br /> System.out.println("start sort.....");<br /> sort.sort();<br /> System.out.println("after sort...");<br /> sort.output();</p> <p> }</p> <p>}<br />