数据结构奇妙旅程之深入解析插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

下面是插入排序的Java实现以及详细的代码解析：

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {4, 3, 2, 10, 12, 1, 5, 6};
        insertionSort(arr);
        System.out.println("Sorted array: ");
        printArray(arr);
    }

    static void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            /* 将arr[i]移动到其正确的位置 */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    /* 打印数组 */
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

代码解析：

1. insertionSort 方法是插入排序的主要实现部分。它接受一个整数数组作为参数，并按升序对数组进行排序。

2. n 是数组的长度，用于控制循环次数。

3. 外层循环 for (int i = 1; i < n; ++i) 从数组的第二个元素开始遍历（索引为1），因为第一个元素默认是已排序的。

4. int key = arr[i]; 将当前要插入的元素保存在 key 变量中。

5. int j = i - 1; 设置 j 为当前元素前一个元素的索引，用于从后向前扫描已排序的序列。

6. 内层循环 while (j >= 0 && arr[j] > key) 用于将大于 key 的元素向后移动一位，为 key 腾出插入的空间。如果 j 小于0或者 arr[j] 小于或等于 key，则退出循环。

7. arr[j + 1] = key; 将 key 插入到正确的位置。

8. 当外层循环结束时，整个数组就被排序了。

9. printArray 方法用于打印数组，用于验证排序结果。

插入排序的时间复杂度在最坏和平均情况下是 O(n^2)，其中 n 是数组的长度。在最好的情况下（数组已经有序），它的时间复杂度为 O(n)。尽管插入排序对于大规模数据来说效率不高，但在处理小规模或部分有序的数据时，它的表现可能还不错。插入排序也是稳定和原地排序算法，这意味着它在排序过程中不会使用额外的空间（除了几个临时变量），并且不会改变相等元素的相对顺序。