二分插入排序JAVA实现

package kpp.sort;
/**
 * 当前待插入元素data[i],若data[i]>=data[i-1],则表示排序正常，i++处理下一个元素
 * 若data[i]<data[i-1]，先保存data[i]至temp,二分查找到适合插入的位置k,从k到i-1的元素顺序右移
 * 将temp插入到k
 * 
 * 分析：
 * 二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数。
 * 当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。
 * 算法的移动次数与直接插入排序算法的相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2)。
 * 
 * @author kpp
 *
 */
public class MiddleInsertSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int array[] = {49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
        midInsertSort(array);
        for(int k :array){
            System.out.println(k);
        }
    }
    private static int midInsertSort(int a[]){
        int len = a.length;
        
        for(int i = 1;i < len;i++){
            //由于插入排序前面的序列是有序的，所以判断当前元素是否比前面元素小，
            //如果小，则做二分插入排序;如果大，则表示当前排序正确，处理下一个元素
            if(a[i] < a[i-1]){
                //先把带插入的值保存起来
                int temp = a[i];
                
                //二分查找待插入位置
                int left = 0;
                int right = i-1;
                int mid = 0;
                
                
                while(left <= right){
                     mid = (right+left)/2;
                     if(temp == a[mid]){
                         left = mid;
                         break;
                     }
                     else if(temp < a[mid]){
                        right = mid -1;
                     }else{
                        left = mid + 1;
                     }
                }
                //待插入位置是left，从left开始，元素统一右移
                for(int j = i-1;j >= left;j--){
                    a[j+1]=a[j];
                }
                
                a[left] = temp;
                
            }
            
        }
        return 0;
    }

}