数据结构：排序之插入排序

时间：2024-03-20 14:31:42

插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。下面是一个详细的Java代码实现，包括每一步的注释，帮助你更好地理解插入排序的过程。

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {4, 3, 2, 10, 12, 1, 5, 6};
        insertionSort(arr);
        printArray(arr);
    }

    // 插入排序方法
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            // 当前需要排序的元素
            int key = arr[i];
            // 已排序序列的最后一个元素的索引
            int j = i - 1;

            // 将大于key的元素后移
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            // 找到key的插入位置并插入
            arr[j + 1] = key;
        }
    }

    // 打印数组的方法
    public 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. main 方法中定义了一个待排序的数组 arr，并调用 insertionSort 方法进行排序，最后调用 printArray 方法打印排序后的数组。

  2. insertionSort 方法是插入排序的核心实现。

    • 外层循环 for (int i = 1; i < n; ++i) 从数组的第二个元素开始遍历，因为第一个元素默认已经是有序的。
    • int key = arr[i]; 取出当前需要排序的元素。
    • 内层循环 while (j >= 0 && arr[j] > key) 从已排序序列的最后一个元素开始向前扫描，如果已排序的元素大于 key，则将该元素后移一位。
    • 当找到合适的插入位置时（即 arr[j] <= key），将 key 插入到该位置。

  3. printArray 方法用于打印数组，方便查看排序结果。

插入排序的时间复杂度在最坏的情况下是O(n2)，即当输入数组是逆序的时候。最好的情况下，当输入数组已经是有序的，时间复杂度是O(n)。平均时间复杂度是O(n2)。空间复杂度是O(1)，因为它只需要一个额外的空间来交换数组元素。尽管插入排序在大数据集上不如更高级的排序算法（如快速排序、归并排序、堆排序等）效率高，但在小数据集上，由于其实现简单且不需要额外的空间，它仍然是一个很好的选择。

相关文章