Java中的插入排序：一种简单且高效的算法

简介

在本博客中，我们将学习插入排序的工作原理。插入排序是一种简单的排序算法，它通过一次一个元素构建最终的排序数组。对于小型数据集，它的效率较高，并且常作为更复杂排序算法的一部分使用。

插入排序的工作原理

• 从数组的第二个元素开始。
• 将其与前面的元素进行比较。
• 如果较小，则将较大的元素向右移动。
• 将该元素插入到正确的位置。
• 对所有元素重复上述步骤。

import java.util.Arrays;
public class InsertionSortExample {
    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;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

时间复杂度

• 最佳情况：O(n)，当数组已经排序时。
• 平均和最坏情况：O(n²)。

空间复杂度

• O(1)，因为它在原地排序。

优点

• 实现简单
• 对于小型数据集效率高
• 自适应（对于部分排序的数组高效）。

缺点

• 对于大型数据集效率低。

总结

插入排序在数据几乎已排序或排序小型数组的场景中表现良好。它的简单性使其成为教育目的和作为更复杂算法的构建块的良好选择。

若你想提升Java技能，可关注我们的Java培训课程。