思路：从左至右把右边新的数据跟左边已排序的数字从右至左逐个排序，遇到条件不满足（大于或小于）时停止交换。
import java.util.*; public class InsertSort { public static int[] sort(int[] x) { int N = x.length; int[] a = new int[N]; for (int i = 0; i < N; i++) a[i] = x[i]; for (int i = 1; i < N; i++) for (int j = i; j >= 1 && less(a, j, j-1); j--) swap(a, j, j-1); return a; } private static boolean less(int[] x, int i, int j) { return x[i] < x[j]; } private static void swap(int[] x, int i, int j) { int t = x[i]; x[i] = x[j]; x[j] = t; } public static void main(String[] args) { Random random = new Random(); int[] a = new int[20]; for (int i = 0; i < 20; i++) a[i] = random.nextInt(100); System.out.println(Arrays.toString(a)); int[] r = sort(a); System.out.println(Arrays.toString(r)); } } /* [42, 63, 92, 76, 10, 99, 75, 78, 0, 8, 84, 52, 54, 16, 97, 30, 39, 76, 50, 9] [0, 8, 9, 10, 16, 30, 39, 42, 50, 52, 54, 63, 75, 76, 76, 78, 84, 92, 97, 99] */