了解插入排序算法（附Java示例）

插入排序是一种迭代排序算法。它通过将每个未排序的元素插入到已排序子数组中的正确位置来构建一个已排序子数组，一次一个元素。 想象一下对一手扑克牌进行排序 - 从一张已排序的牌开始，然后将后续的每张牌插入已排序的牌中的正确位置。

插入排序如何工作

让我们用一个要按升序排序的示例数组来说明：

第一次迭代：

我们认为第一个元素已经排序。 该算法从第二个元素开始。

比较 2 和 8，因为 2

第二次迭代：

我们将 6 与排序后的子数组 (2, 8) 进行比较。 6＜ 8，所以 8 右移。 那么，由于 6 > 2, 6 位于 2 的右侧。

此过程将持续进行，直到整个数组完成排序。

Java 中的实现

import java.util.Arrays;

public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; 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;
        }
    }
}

代码进行迭代，将每个元素作为 key。 然后，它将 key 与已排序部分中的元素进行比较，将较大的元素向右移动，直到找到 key 的正确位置。

例如，在第二次迭代中（i=2）：

key 为 6。while 循环移动元素，直到找到正确的位置：

最后插入6：

输出：

未排序数组：[8,2,6,4,9,1] 排序数组：[1, 2, 4, 6, 8, 9]

复杂性分析

• 时间复杂度：
  • 最佳情况 (O(n))：已经排序的数组。
  • 平均情况 (O(n²))：随机排列的元素。
  • 最坏情况 (O(n²))：逆序数组。
• 空间复杂度：O(1)（就地算法）

结论

插入排序的二次时间复杂度使其对于大型数据集效率低下。 然而，它是一个简单的算法，并且在小数据集或接近排序的数据上表现良好。

以上是了解插入排序算法（附Java示例）的详细内容。更多信息请关注PHP中文网其他相关文章！