算法-插入排序

• 记于：2026-04-01 上午
• 地点：浙江省·温州市·家里
• 天气：多云

• 简介
• 实现

• 参考

简介#

插入排序是一种简单的排序算法，它的工作原理是通过将一个元素插入到已排序的子序列中，来实现排序。
将其想象成手中扑克牌的排序过程，这样就比较直观了。

实现#

/**
 * 插入排序
 */
public class InsertionSort {

    public static void main(String[] args) {
        // 生成100个待排序随机数
        int[] arr = randomArray(100); 

        // 打印排序前的数组
        System.out.println("before sort: ");
        print(arr);

        // 排序
        long t1 = System.currentTimeMillis();
        int[] arr2 = insertionSort(arr);
        long t2 = System.currentTimeMillis();
        System.out.println("\ntime: " + (t2 - t1) + "ms");

        // 打印排序后的数组
        System.out.println("after sort: ");
        print(arr2);
        System.out.println();
    }

    public static int[] insertionSort(int[] arr) {
        // 从第2个开始遍历
        for (int i = 1; i < arr.length; i++) {
           // 往左边对比，直到找到比它大的或者到头
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    // swap
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                } else {
                    break;
                }
            }
        }
        return arr;
    }

    // print
    public static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static int[] randomArray(int n) {
        if (n <= 0) {
            return new int[0];
        }

        int[] arr = new int[n];

        // 1. 初始化 1~n
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }

        // 2. 洗牌
        java.util.Random random = new java.util.Random();
        for (int i = n - 1; i > 0; i--) {
            int j = random.nextInt(i + 1); // [0, i]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        return arr;
    }
}

主要见 insertionSort 方法。
思路：

1. 从第2个元素遍历，与左边的元素对比。
2. 如果当前元素小于左边的元素，交换它们的位置。
3. 继续对比左边的元素，直到找到比它大的或者到头。

参考#

• 《算法导论》