Java经典排序算法之插入排序

插入排序算法简介

插入排序是一种简单直观的排序算法，它的基本思想是将待排序序列分为已排序和未排序两部分，初始时将第一个元素视为已排序序列，将其他元素视为未排序序列。然后依次将未排序序列中的元素插入到已排序序列中的正确位置。在插入元素时，需要从右到左比较已排序序列中的元素，找到插入元素的正确位置。

插入排序算法示例

假设我们要对以下数组进行排序：[3, 1, 4, 2, 5]。

1. 初始时，我们将第一个元素3视为已排序序列，将其他元素1、4、2、5视为未排序序列。

3 | 1 4 2 5

1. 取出未排序序列中的第一个元素1，将它插入到已排序序列中的正确位置。由于1比3小，因此1应该插入到3的左侧。

1 3 | 4 2 5

1. 取出未排序序列中的下一个元素4，将它插入到已排序序列中的正确位置。由于4比3大，因此4应该插入到3的右侧。

1 3 4 | 2 5

1. 接着取出未排序序列中的下一个元素2，将它插入到已排序序列中的正确位置。由于2比4小，因此2应该插入到4的左侧，而4又比3大，因此2应该插入到3的左侧。

1 2 3 4 | 5

1. 最后取出未排序序列中的最后一个元素5，将它插入到已排序序列中的正确位置。由于5比4大，因此5应该插入到4的右侧。

1 2 3 4 5 |

经过以上步骤，我们成功地对数组进行了排序。

Java代码实现

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

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

在上面的代码中，我们使用了一个外层循环，它遍历了整个待排序数组。对于数组中的每个元素，我们都将它插入到已排序序列中的正确位置。

在内层循环中，我们从右向左比较已排序序列中的元素，找到插入位置。如果已排序序列中的元素比当前元素大，则将它们向右移动一位，为当前元素腾出插入位置。最后将当前元素插入到正确位置即可。

复杂度分析

插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。当序列基本有序时，插入排序的效率较高，而当序列完全无序时，插入排序的效率很低。因此，插入排序一般适用于小规模的序列排序。