java实现直接插入排序和二分法插入排序

• 直接插入排序：第i趟排序将第i+1个元素temp插入到0-i的有序序列当中。将temp与0-i个有序元素向前进行比较，当0-i有序元素中的第j个元素小于temp时，将第j+1至i个元素向后移动一位，同时将temp插入到j+1中。重复上述步骤i趟完成排序。

• 二分法插入排序：将上述temp与0-i个有序元素进行比较更改为使用二分查找找到temp插入的下标，减少比较次数，但移动次数不变。

  public class InsertSort {
  
    private static void insertSort1(int[] a){
        //i为排序第i趟，同时为已经有序的数据序列的右边界元素；temp为该趟需要插入的元素
        for (int i = 0;i < a.length-1;i++){
            int temp = a[i + 1],j;
            //j代表temp与有序序列进行比较的下标，从有序序列最后一个元素开始
            for (j = i;j >= 0 && a[j] > temp;j--){
                a[j + 1] = a[j];
            }
            a[j + 1] = temp;
        }
    }
  
    private static void insertSort2(int[] a){
        //i为排序第i趟，同时为已经有序的数据序列的右边界元素；temp为该趟需要插入的元素
        for (int i = 0;i < a.length-1;i++){
            int temp = a[i + 1],j;
            //j代表temp与有序序列进行比较的下标，从有序序列最后一个元素开始
            for (j = i;j >= 0;j--){
                if (a[j] > temp){
                    a[j + 1] = a[j];
                }else{
                    break;
                }
            }
            a[j + 1] = temp;
        }
    }
  
    /**
     * 二分法插入排序
     * @param a 待排序数组
     */
    private static void binaryInsertSort(int[] a){
        //i为排序第i趟，同时为已经有序的数据序列的右边界元素；temp为该趟需要插入的元素
        for (int i = 0;i < a.length - 1;i++){
            int temp = a[i + 1];
            int start = 0;
            int end = i;
            while (start <= end){
                int mind = (end + start)/2;
                if (a[mind] > temp){
                    end = mind - 1;
                }else{
                    start = mind + 1;
                }
            }
            int j = i;
            //j代表temp与有序序列进行比较的下标，从有序序列最后一个元素开始至二分查找的start下标止
            //只有当temp小于有序序列边界元素时才发生移动，移动到下标start为止
            for (;j >= start && a[i] > temp;j--){
                a[j + 1] = a[j];
            }
            //当temp小于有序序列边界元素时，说明发生移动，将temp插入到start下标为止
            if (a[i] > temp){
                a[start] = temp;
            }
        }
    }
  
    public static void main(String[] args) {
        int[] a = new int[]{32,26,87,72,26,17,20,29,71,65,45,34,98,101,75,49,28,34,57,47,64,11,23,68,91};
        int[] b = new int[]{32,26,87,72,26,17,20,29,71,65,45,34,98,101,75,49,28,34,57,47,64,11,23,68,91};
        int[] c = new int[]{32,26,87,72,26,17,20,29,71,65,45,34,98,101,75,49,28,34,57,47,64,11,23,68,91};
  
        insertSort1(a);
        insertSort2(b);
        binaryInsertSort(c);
  
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(b));
        System.out.println(Arrays.toString(c));
    }
  }
  

[11, 17, 20, 23, 26, 26, 28, 29, 32, 34, 34, 45, 47, 49, 57, 64, 65, 68, 71, 72, 75, 87, 91, 98, 101]
[11, 17, 20, 23, 26, 26, 28, 29, 32, 34, 34, 45, 47, 49, 57, 64, 65, 68, 71, 72, 75, 87, 91, 98, 101]
[11, 17, 20, 23, 26, 26, 28, 29, 32, 34, 34, 45, 47, 49, 57, 64, 65, 68, 71, 72, 75, 87, 91, 98, 101]