算法与数据结构-插入排序

思想：简单插入排序是每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，若是序列是正序，时间复杂度为O(n), 序列越是基本有序，简单插入排序越是快

public class DemoApplication {
    public static void main(String[] args) {
        int arr[] = {6, 4, 8, 9, 2, 3, 1};
        insertionSort(arr);
        
        for(int k = 0; k < arr.length; k++){
            System.out.print(arr[k] + ",");
        }
    }
    
    public static int binarySearch(int[] arr, int n, int target){
        int left = 0;
        int right = n;
        while(left <= right){
            int middle = (left + right) >> 1;
            if(arr[middle] >= target){
                right = middle - 1;
            }else{
                left = middle + 1;
            }
        }
        return left <= n ? left : -1;
    }
    
    public static void insertionSort(int arr[]){
        for(int i = 1; i < arr.length; i++){
            //二分法查找
            int s = binarySearch(arr, i - 1, arr[i]);
            if(s != -1){
                int t = arr[i];
                int j = i;
                while(s < j){
                    arr[j] = arr[j - 1];
                    j--;
                }
                arr[s] = t;
            }
        }
    }
  
}

参考地址：排序算法(3) -- 插入排序_Dby_freedom的博客-CSDN博客