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

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