排序—直接插入排序与二分查找排序(Java)

算法描述：

① 从第一个元素开始，该元素可以认为已经被排序；

② 取出下一个元素，在已经排序的元素序列中从后向前扫描；

③ 如果该元素（已排序）大于新元素，将该元素移到下一位置；

④ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

⑤ 将新元素插入到该位置后，重复步骤2~5。

public class Sort{
    
    //直接插入排序
    public static int[] insertSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            int j = i-1;
            int temp = arr[i];
            while(j >= 0 && arr[j] > temp){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp; 
        }
        return arr;
    }
    
    //二分查找
    public static int binaryRearch(int[] arr, int temp, int low, int hight){
        if(low >= hight){
            return temp > arr[low] ? (low + 1) : low;
        }
        int mid = (low + hight) / 2;
        if(arr[mid] == temp){
            return mid + 1;
        }else if(arr[mid] > temp){  
            return binaryRearch(arr, temp, low, mid - 1);
        }else{
            return binaryRearch(arr, temp, mid + 1, hight);
        }
    }
    
    //二分插入排序
    public static int[] binaryInsertSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            int temp = arr[i];
            int j = i-1;
            int index = binaryRearch(arr, temp, 0, j);
            while(j >= index) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = temp;  
        }
        return arr;
    }
    
    public static void main(String[] args){
        
        System.out.println("=====插入排序=====");
        int[] array = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        System.out.println("排序之前：");
        for(int i = 0; i < array.length; i++){
            System.out.print(array[i] + " ");
        }
        
        //直接插入排序
        array = insertSort(array);
        
        //二分插入排序
        array = binaryInsertSort(array);
        
        System.out.println("\n");
        System.out.println("排序之后：");
        for(int i = 0; i < array.length; i++){
            System.out.print(array[i] + " ");
        }
    }
}