文章摘要： 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

简介

简要说明

  • 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
  • 插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。

主要功能

  • 将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

注意事项

  • 插入排序对于小数据集是效率很高的，在数据量较小的情况下，这是一个很好的排序算法。
  • 插入排序是稳定的排序算法，不会改变相同元素的相对顺序。

适用场景

  • 数据量小。
  • 部分有序的数组。

时间复杂度

  • 最优情况（已排序）：O(n)
  • 平均、最坏情况：O(n^2)

空间复杂度

  • O(1)，插入排序是原地排序算法。

Java 8

public class InsertionSort {

    // 主方法调用插入排序
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6};
        insertionSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }

    // 插入排序方法
    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;

            // 将array[i]与已排序好的array[0...i-1]中的元素比较，找到合适的位置插入
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j]; // 将元素向后移动，为插入元素腾出空间
                j = j - 1;
            }
            array[j + 1] = key; // 将元素插入到正确的位置
        }
    }
}

注释

在这个Java案例中，insertionSort 方法实现了插入排序算法。从数组的第二个元素开始，将其与前面的元素比较，如果当前元素小于比较的元素，则将比较的元素向后移动，直到找到正确的插入位置。这个过程一直重复，直到整个数组排序完成。

更新时间: