Java数据结构及算法实例：插入排序 Insertion Sort

算法简介

插入排序是一种简单的排序算法，它的工作方式是每次将一个待排序的元素与前面已经排好序的元素逐个比较，并插入到合适的位置。插入排序的时间复杂度为O(n^2)，是一种比较低效的排序算法。

算法实现

以下是使用Java语言实现插入排序算法的代码：

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

对于一个长度为n的数组，插入排序算法将会执行n-1次循环。每次循环都将一个待排序的元素插入到前面已经排好序的序列中。其中，内层的while循环会将待排序元素与前面的所有元素逐一比较，直到找到合适的位置。最后，该元素会被插入到正确的位置。

算法示例

以下是两个简单的例子来说明插入排序算法的过程：

示例1

对于数组arr=[3, 1, 5, 2, 4]，使用插入排序算法进行排序的过程如下：

1. 第1次循环，将1插入到合适的位置，序列变为[1, 3, 5, 2, 4]
2. 第2次循环，将5插入到合适的位置，序列变为[1, 3, 5, 2, 4]
3. 第3次循环，将2插入到合适的位置，序列变为[1, 2, 3, 5, 4]
4. 第4次循环，将4插入到合适的位置，序列变为[1, 2, 3, 4, 5]

最终排序结果为[1, 2, 3, 4, 5]。

示例2

对于数组arr=[5, 4, 3, 2, 1]，使用插入排序算法进行排序的过程如下：

1. 第1次循环，将4插入到合适的位置，序列变为[4, 5, 3, 2, 1]
2. 第2次循环，将3插入到合适的位置，序列变为[3, 4, 5, 2, 1]
3. 第3次循环，将2插入到合适的位置，序列变为[2, 3, 4, 5, 1]
4. 第4次循环，将1插入到合适的位置，序列变为[1, 2, 3, 4, 5]

最终排序结果为[1, 2, 3, 4, 5]。

总结

插入排序算法是一种简单且易于理解的排序算法，它的核心思想是将待排序元素插入到前面已经排好序的序列中。但是，插入排序算法的时间复杂度为O(n^2)，对于大规模的数据排序来说效率较低。因此，在实际应用中需要根据数据规模和性能要求选择合适的排序算法。