相较于插入排序，每次寻找插入位置时将线性扫描变为二分查找，时间复杂度从O(n)变为O(lgn)
    时间复杂度：O(n^2)
    虽然省去了查找位置的过程，但还是需要移动数组

    1. import java.util.*;
    3. public class Main {
    4.     public static void main(String[] args) {
    5.         Scanner sc = new Scanner(System.in);
    7.         int n = sc.nextInt();
    8.         int[] a = new int[n];
    10.         for (int i = 0; i < n; i++)
    11.             a[i] = sc.nextInt();
    13.         for (int i = 1; i < a.length; i++) {
    14.             int key = a[i];
    15.             int l = 0, r = i - 1;
    16.             if (key >= a[r])
    17.                 continue;
    18.             while (l < r) {
    19.                 int mid = l + (r - l >> 1);
    20.                 if (a[mid] <= key)
    21.                     l = mid + 1;
    22.                 else
    23.                     r = mid;
    24.             }
    25.             for (int j = i; j > l; j--)
    26.                 a[j] = a[j - 1];
    27.             a[l] = key;
    28.         }
    30.         for (int i = 0; i < n; i++) {
    31.             System.out.print(a[i] + " ");
    32.         }
    33.     }
    34. }