一.插入排序（Insertion Sort）是一种简单直观的排序算法，适合于少量数据的排序。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是用Java实现插入排序的代码及其详细讲解。

二.插入排序代码

public class InsertionSort {

    public static void insertionSort(int[] array) {
        int n = array.length;

        // 从第二个元素开始遍历数组
        for (int i = 1; i < n; i++) {
            int key = array[i]; // 当前要插入的元素
            int j = i - 1;

            // 在已排序部分中从后向前扫描，找到合适的位置插入
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j]; // 将元素向后移动
                j--;
            }
            array[j + 1] = key; // 插入元素
        }
    }

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6};
        System.out.println("Unsorted array:");
        printArray(array);

        insertionSort(array);

        System.out.println("Sorted array:");
        printArray(array);
    }

    private static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

三.详细讲解

• 初始化:

• n是数组的长度。

• 外层循环:

• 从第二个元素开始遍历数组（i = 1），因为第一个元素默认是已排序的。

• key是当前要插入的元素。

3. 内层循环:

• j初始化为i - 1，表示已排序部分的最后一个元素。

• 从后向前扫描已排序部分，比较key与array[j]。

• 如果array[j]大于key，则将array[j]向后移动一位。

• 继续向前扫描，直到找到一个不大于key的元素或到达数组的开头。

4. 插入元素:

• 将key插入到正确的位置，即array[j + 1]。

• 打印数组:

• printArray方法用于打印数组的内容。

总结

插入排序的时间复杂度为O(n²)，因为在最坏情况下需要进行n²次比较和移动。然而，对于小规模数据集或部分有序的数据集，插入排序可能比其他O(n²)排序算法（如选择排序、冒泡排序）更有效。插入排序的优点是它的实现简单，并且在排序过程中可以保持相同元素的相对顺序（稳定性）。