Java实现直接插入排序算法教程及源码

直接插入排序是一种基本的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。它是实现简单、效率稳定、应用广泛的排序方法之一，尤其适用于小规模数据的排序。在本节中，将详细介绍Java语言实现的直接插入排序算法的源码，包括代码中的注释，以便于对Java新手理解和学习。 首先，直接插入排序算法的核心步骤包括： 1. 从第一个元素开始，该元素可以认为已经被排序。 2. 取下一个元素，在已经排序的元素序列中从后向前扫描。 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。 5. 将新元素插入到该位置后。 6. 重复步骤2~5。 在Java中实现直接插入排序算法的代码大致如下： ```java public class InsertionSort { /** * 直接插入排序 * * @param arr 待排序数组 */ public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { // 记录当前要插入的元素 int current = arr[i]; int j = i - 1; // 查找插入的位置 while (j >= 0 && arr[j] > current) { arr[j + 1] = arr[j]; j--; } // 插入元素 arr[j + 1] = current; } } // 主函数用于测试 public static void main(String[] args) { int[] array = {9, 3, 1, 5, 13, 12, 10}; insertionSort(array); for (int num : array) { System.out.print(num + " "); } } } ``` 在这段代码中，`insertionSort` 方法是直接插入排序算法的具体实现。它首先检查输入的数组是否为空或只含有一个元素，如果是，则不进行排序，直接返回。然后，算法进入一个外层循环，从数组的第二个元素开始遍历到数组的末尾。对于每个元素，我们将其视为需要插入到已排序部分的元素（`current`），然后从数组尾部向前比较，找到插入位置（即找到一个比`current`小的元素），并将大于`current`的元素向后移动，直到找到插入点。最后将`current`插入到找到的位置。 在代码的主函数`main`中，我们创建了一个未排序的整型数组`array`，调用`insertionSort`方法进行排序，然后遍历并打印排序后的数组元素，以便验证排序是否成功。 直接插入排序算法适用于数据量不大的情况，对于大数据集，其时间复杂度较高，尤其是当元素基本呈反序时，会退化到O(n^2)。尽管如此，由于它的实现简单和运行效率较高，在小数据量的场合下，仍然是一个非常实用的算法。同时，由于它是一个稳定的排序算法，所以在需要稳定性的应用中，直接插入排序也是一个不错的选择。