插入排序的 Java 代码实现。

InsertSort.java

package test;

import java.util.Arrays;
import java.util.Random;

public class InsertSort {
    private static Random random = new Random(System.currentTimeMillis());

    /**
     * 判断给定的数组是不是已经排好序的数组
     *
     * @param arr
     */
    private static void checkSorted(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                throw new RuntimeException("数组不是排好序的");
            }
        }
    }

    /**
     * @param count 数组中元素的个数
     * @param mix   最小值能取到
     * @param max   最大值取不到
     * @return
     */
    private static int[] generateRamdonArray(int count, int mix, int max) {
        int[] arr = new int[count];
        int bound = max - mix;
        for (int i = 0; i < count; i++) {
            int randomInt = random.nextInt(bound) + mix;
            arr[i] = randomInt;
        }
        return arr;
    }

    private static void swap(int[] arr, int index1, int index2) {
        if (index1 == index2) return;
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static void main(String[] args) {
        // 插入排序(内层循环可以提前终止)
        int[] arr = generateRamdonArray(15, 10, 100);
        System.out.println("原始数组" + Arrays.toString(arr));

        int len = arr.length;
        for (int i = 0; i < len - 1; i++) { // 第 1 轮的时候，第 1 个数可以认为是排好序的
            for (int j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
        checkSorted(arr);
        System.out.println("排好序的数组" + Arrays.toString(arr));
    }
}