二分排序java實現

1.什么是二分排序：

二分排序是指利用二分法的思想對插入排序進行改進的一種插入排序算法，不同于二叉排序，可以利用數組的特點快速定位指定索引的元素；

算法思想：二分法插入排序是在插入第i個元素時，對前面的0～i-1元素進行折半，先跟他們中間的那個元素比，如果小，則對前半再進行折半，否則對后半進行折半，直到left>right，然后再把第i個元素前1位與目標位置之間的所有元素后移，再把第i個元素放在目標位置上。

2.這是普通的插入排序java實現：

    public static void insertSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            int j = i;
            int k = j-1;
            while(k>=0){
                if(arr[k]>arr[j]){
                    int tmp = arr[k];
                    arr[k] = arr[j];
                    arr[j] = tmp;
                    j--;
                    k--;
                }else{
                    break;
                }
            }
        }
    }

3.二分排序java代碼實現如下：

    public static void binarySort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int left= 0;
            int right= i-1;
            int pivot = (left+right)/2;
            while(left<right){
                while(left<right){
                    if(arr[pivot]>arr[i]){
                        right = pivot-1;
                        pivot = (left+right)/2;
                    }else{
                        break;
                    }
                }
                while(left<right){
                    if(arr[pivot]<arr[i]){
                        left = pivot+1;
                        pivot = (left+right)/2;
                    }else{
                        break;
                    }
                }
            }
            if(left>=right){
                if(arr[pivot]<arr[i]){
                    pivot++;
                }
                int j = i;
                int k = j-1;
                while(k>=pivot){
                    int tmp = arr[j];
                    arr[j] = arr[k];
                    arr[k] = tmp;
                    j--;
                    k--;
                }
            }
        }
        
    }

?二分排序的時間復雜度：O(n^2)，空間復雜度：O(1)