数据结构-插入排序Java实现

一、引言

    插入排序是一种基本的比较排序算法，其核心思想是将数组分为已排序和未排序两部分，然后逐个将未排序的元素插入到已排序部分的适当位置。这个过程重复进行，直到整个数组都排好序。插入排序的时间复杂度为O(n^2)，适用于小型数据集或接近有序的数据。

二、算法步骤

插入排序的基本步骤如下：

1. 将数组分为已排序部分和未排序部分，初始状态下已排序部分只包含数组的第一个元素，而未排序部分包含其余元素。
2. 从未排序部分选择一个元素，将其与已排序部分的元素逐个比较，找到合适的位置，使得已排序部分仍然保持升序排列。
3. 插入该元素到已排序部分的正确位置。
4. 重复步骤2和3，直到未排序部分为空，即整个数组都被排序。

三、原理演示

假设我们有以下整数数组：
[64, 34, 25, 12, 22, 11, 90]

• 第一轮：
  在第一轮中，整个数组被分为已排序部分和未排序部分。初始状态下，已排序部分只包含第一个元素 [64]，而未排序部分包含其余元素 [34, 25, 12, 22, 11, 90]。
  首先，选择未排序部分的第一个元素 34。
  将 34 与已排序部分的元素 64 进行比较。由于 34 小于 64，我们将 64 向右移动一个位置，然后 34 插入到 64 的位置。
  数组变为：已排序部分 [34, 64]，未排序部分 [25, 12, 22, 11, 90]。
• 第二轮：
  选择未排序部分的第一个元素 25。
  将 25 与已排序部分的元素 64 进行比较。由于 25 小于 64，我们将 64 向右移动一个位置。接着，将 25 与 34 进行比较，由于 25 小于 34，我们将 34 也向右移动一个位置。
  最后，将 25 插入到已排序部分的适当位置。
  数组变为：已排序部分 [25, 34, 64]，未排序部分 [12, 22, 11, 90]。
  以此类推，继续进行下一轮，直到整个数组都被排序。
• 最后一轮：
  在最后一轮中，未排序部分的元素 11 和 90 会被逐个插入到已排序部分的适当位置，最终完成整个数组的排序。整个数组变为有序状态。

插入排序的关键思想是在未排序部分中选择元素，然后将其插入到已排序部分的适当位置，以构建有序数组。这个过程反复进行，直到整个数组都被排序。

四、代码实战

下面是使用Java编写的插入排序算法示例：

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        System.out.println("原始数组：");
        printArray(arr);

        insertionSort(arr);

        System.out.println("排序后的数组：");
        printArray(arr);
    }

    // 插入排序实现
    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;

            // 将arr[i]插入已排序部分的适当位置
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }
    }

    // 辅助方法，用于打印数组
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

上述代码演示了插入排序的实现。它首先定义了一个包含整数数组的示例，然后调用 insertionSort 方法来对数组进行排序。insertionSort 方法通过将未排序部分的元素插入已排序部分的适当位置来实现插入排序。

五、结论

我们一起来总结一下：

1. 插入排序的基本思想是将待排序的元素插入到已排序的元素中的适当位置，以达到排序的目的。
2. 插入排序的时间复杂度为O(n^2)，其中n为待排序元素的个数。这是因为在最坏情况下，插入排序需要进行n-1次插入操作。
3. 插入排序的空间复杂度为O(1)，因为只需要使用一个额外的变量来存储临时元素。
4. 插入排序是稳定的排序算法，即相同元素的相对位置在排序后不会改变。
5. 插入排序在处理小规模数据集时表现良好，但是对于大规模数据集，由于其时间复杂度较高，因此效率较低。
6. 在实际应用中，如果需要排序的数据量较大，通常会优先考虑使用其他更高效的排序算法，如快速排序、归并排序等。但是，对于部分有序的数据，插入排序可以表现出较好的性能。
7. 在外部排序（即不能一次性将所有数据装入内存）的情况下，插入排序是一个非常好的选择。这种情况下，通常采用“外部插入排序”的方法，通过将数据一部分一部分地读入内存，然后进行排序。
8. 通过使用二分查找法（Binary Search）进行搜索定位，可以使插入排序在数据量较大的情况下仍具有较高的效率。在这种情况下，该算法被视为“二分插入排序”。

点赞收藏，富婆包养✋✋