插入排序--折半插入排序
一，实现方法一
public void sort(int[] a){int temp,low,mid,height,k;for(int i=1;i<a.length;i++){low=0;height=i-1;mid=i;while(low<=height){mid=(low+height)/2;if(a[i]>=a[mid])low=mid+1;elseheight=mid-1;}temp=a[i];for(k=i-1;k>=low;k--)a[k+1]=a[k];a[k+1]=temp;}}public void sort(int[] a){int temp;int low,height,mid;for(int i=1;i<a.length;i++){low=0;height=i-1;mid=i;while(low<height){mid=(low+height)/2;if(a[i]>a[mid])low=mid+1;elseheight=mid;}if(a[i]<=a[low]){temp=a[i];for(int k=i-1;k>=low;k--)a[k+1]=a[k];a[low]=temp;}}}public void sort(int[] a){int temp;int loc;int j;for(int i=1;i<a.length;i++){loc=middle(a,0,i-1,a[i]);if(a[loc]>=a[i]){temp=a[i];for(j=i-1;j>=loc;j--)a[j+1]=a[j];a[j+1]=temp;}}}private int middle(int a[], int low, int height, int key){int mid = (low+height)/2;if(a[mid]==key)return mid;if(a[mid]<key && low<height){low=mid+1;return middle(a,low,height,key);}if(a[mid]>key && low<height){height=mid;return middle(a,low,height,key);}return height;}