java常见算法 插入排序

插入排序（Insertion Sort）是一种简单的排序算法，其基本思想是将未排序部分的元素逐个插入到已排序部分的合适位置，从而形成新的有序部分。具体步骤如下：

1. 从数组的第二个元素开始，将其视为已排序部分。
2. 依次将未排序部分的元素插入到已排序部分的合适位置。为了找到插入位置，将当前元素与已排序部分的元素进行比较，如果当前元素小于已排序部分的某个元素，则将该元素后移，直到找到合适的插入位置。
3. 将当前元素插入到找到的插入位置，将已排序部分的长度加一。
4. 重复上述步骤，直到所有元素都插入到已排序部分。

下面是使用Java实现的插入排序算法：

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

在上述代码中，arr是待排序的数组。从第二个元素开始，通过循环遍历未排序部分的元素，将其与已排序部分的元素进行比较。如果当前元素小于已排序部分的某个元素，则将该元素后移，直到找到合适的插入位置。最后，将当前元素插入到找到的插入位置，并更新已排序部分的长度。

插入排序的时间复杂度为O(n^2)，其中n为数组的长度。尽管插入排序的时间复杂度较高，但对于小规模或基本有序的数组，插入排序是一种简单且高效的排序算法。然而，在面对大规模乱序的数组时，更高效的排序算法如快速排序和归并排序通常更为合适。

原文链接：codingdict.net