Java：插入排序

插入排序是一种简单而直观的排序算法，其主要思想是将待排序列分为已排序和未排序两部分，然后逐步将未排序的元素插入到正确的位置，以此实现对整个序列的排序。由于其简单性，插入排序在小规模数据集上表现良好，且实现起来也较为容易。

插入排序的基本思想

插入排序的过程中，我们维护一个已排好序的子序列，从第二个元素开始，每次取出未排序的元素，通过与已排序元素的比较，找到其合适的位置并插入。对于已经排好序的子序列，我们需要从后往前遍历，直到找到比当前元素小的元素位置或遍历到序列的开头。

插入排序的步骤

1. 从第二个元素开始，假设第一个元素已经是一个有序序列。
2. 取出当前元素，在已排序序列中从后向前遍历，找到比当前元素小的位置。
3. 将较大的元素向后移，为当前元素腾出位置。
4. 将当前元素插入到合适的位置。
5. 重复以上步骤，直至所有元素都被插入。

代码实现

以下是插入排序的Java代码实现：

public class InsertionSort {

    public static void insertionSort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            int current = array[i]; // 当前待插入的元素
            int j = i - 1;

            // 在已排序的子序列中找到插入位置
            while (j >= 0 && array[j] > current) {
                array[j + 1] = array[j]; // 将元素向后移动
                j--;
            }
            array[j + 1] = current; // 插入元素
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        System.out.println("排序前的数组：");
        printArray(array);

        insertionSort(array);

        System.out.println("排序后的数组：");
        printArray(array);
    }

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

代码解析

在上述代码中，insertionSort方法实现了插入排序算法。首先定义了一个外层循环，用于遍历每个待排序的元素。对于每个元素，我们使用一个内层循环从已排序的部分从后向前查找插入位置。在找到插入位置后，将当前元素插入到合适的位置。

时间复杂度与空间复杂度

插入排序的时间复杂度为O(n^2)，在最坏情况下（即反向排列情况）可能出现最差的表现。而最佳情况下（即数组已经是有序时），其时间复杂度则为O(n)。空间复杂度为O(1)，因为它是一个原地排序算法。

适用场景

由于插入排序在小规模数据上性能良好，特别是在数据有部分有序的情况下，插入排序的表现会优于复杂的排序算法。此外，插入排序也是在线性时间内可以解决的问题，例如合并已经排好序的两个小数组，这时只需简单地插入元素即可。

综上所述，插入排序是一种简单易懂且有效的排序算法，适合处理小规模数组或部分有序数组。通过理解其工作原理，我们可以更好地掌握排序算法的基础。