插入排序算法详解及其实现代码

由 Java Q&A Hub 使用 GPT-4o-mini 回答

问题：

插入排序

回答：

插入排序（Insertion Sort）是一种简单直观的排序算法，它的基本思想是将待排序的元素逐个插入到已经排好序的部分中，从而形成一个有序序列。插入排序的时间复杂度为 (O(n^2))，在数据量较小或部分有序的情况下表现良好。

插入排序的工作原理

  1. 从第二个元素开始，假设第一个元素已经是有序的。
  2. 将当前元素与前面的元素进行比较，找到合适的位置插入当前元素。
  3. 将比当前元素大的元素向后移动一位，为当前元素腾出位置。
  4. 重复步骤2和3，直到所有元素都被插入到正确的位置。

插入排序的伪代码

for i from 1 to length(A) - 1 do
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key do
        A[j + 1] = A[j]
        j = j - 1
    A[j + 1] = key
end for

Java 实现插入排序

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

public class InsertionSort {
    public static void insertionSort(int[] array) {
        // 从第二个元素开始
        for (int i = 1; i < array.length; i++) {
            int key = array[i]; // 当前要插入的元素
            int j = i - 1;

            // 找到插入位置
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j]; // 向后移动元素
                j--;
            }
            array[j + 1] = key; // 插入当前元素
        }
    }

    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();
    }
}

代码分析

  1. 方法定义：insertionSort 方法接受一个整数数组作为参数。
  2. 外层循环：从数组的第二个元素开始（索引1），逐个处理每个元素。
  3. 内层循环：使用 while 循环找到当前元素 key 的插入位置。条件是 j 大于等于0且 array[j] 大于 key，如果条件成立，则将 array[j] 向后移动一位。
  4. 插入元素：当找到合适的位置后，将 key 插入到 array[j + 1]。
  5. 打印数组：printArray 方法用于输出数组的内容。

时间复杂度

  • 最坏情况：当数组是逆序时，插入排序需要进行 (O(n^2)) 次比较和移动。
  • 最好情况：当数组已经是有序的，插入排序只需要 (O(n)) 次比较。
  • 平均情况：插入排序的平均时间复杂度为 (O(n^2))。

空间复杂度

插入排序是原地排序算法，空间复杂度为 (O(1))，因为只需要常量级的额外空间来存储临时变量。

总结

插入排序是一种简单易懂的排序算法，适合小规模数据的排序。在实际应用中，插入排序常常作为其他更复杂排序算法的基础部分，尤其是在处理小规模数据时。

Related