相较于插入排序,每次寻找插入位置时将线性扫描变为二分查找,时间复杂度从O(n)变为O(lgn)
时间复杂度:O(n^2)
虽然省去了查找位置的过程,但还是需要移动数组
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = sc.nextInt();
for (int i = 1; i < a.length; i++) {
int key = a[i];
int l = 0, r = i - 1;
if (key >= a[r])
continue;
while (l < r) {
int mid = l + (r - l >> 1);
if (a[mid] <= key)
l = mid + 1;
else
r = mid;
}
for (int j = i; j > l; j--)
a[j] = a[j - 1];
a[l] = key;
}
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
}
}