java 直接插入排序

直接插入排序是一种简单直观的排序算法，它的工作原理是通过构造一个有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这种算法在最坏的情况下，时间复杂度为O(n^2)，但在最好情况下，如输入数组已经是有序的，时间复杂度可以达到O(n)。在实际应用中，直接插入排序通常适用于小规模或者部分有序的数据。 下面我们将详细探讨Java实现的直接插入排序算法： 1. **算法步骤** - 初始化：设置一个空的有序序列，将第一个元素视为已排序。 - 遍历：从第二个元素开始遍历数组，将其称为当前元素。 - 比较：将当前元素与已排序序列的最后一个元素进行比较。 - 插入：如果当前元素小于已排序序列的最后一个元素，则将已排序序列的所有元素向右移动一位，为当前元素腾出位置；然后将当前元素插入到正确的位置。 - 重复：继续遍历剩余未排序的元素，重复以上步骤，直到所有元素都插入到有序序列中。 2. **Java代码实现** - 在Java中，我们可以创建一个名为`InsertionSort`的类，其中包含一个静态方法`sort`来执行排序操作。我们需要声明一个整型数组`arr`来存储待排序的元素，然后使用嵌套循环实现插入排序算法。 ```java public class InsertionSort { public static void sort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; // 将大于key的元素向后移动 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } // 插入key arr[j + 1] = key; } } // 打印数组 public static void printArray(int[] arr) { for (int i : arr) { System.out.print(i + " "); } System.out.println(); } public static void main(String[] args) { int[] array = {9, 6, 3, 1, 8, 5, 2, 7, 4}; // 待排序的数组 System.out.println("原始数组:"); printArray(array); sort(array); System.out.println("排序后的数组:"); printArray(array); } } ``` 3. **性能分析** - 时间复杂度：平均和最坏情况下的时间复杂度都是O(n^2)，因为每个元素都需要可能与前面的所有元素进行比较。 - 空间复杂度：由于算法是原地排序，不使用额外的存储空间，所以空间复杂度为O(1)。 - 稳定性：直接插入排序是稳定的排序算法，即相等的元素不会改变它们原有的相对顺序。 总结，直接插入排序是一种基础且易于理解的排序算法，虽然其效率不如更高级的算法如快速排序或归并排序，但对于小规模数据或部分有序的数据，它的性能表现还是相当不错的。在实际编程中，我们应根据具体情况选择合适的排序算法。在学习和分享中，我们可以不断优化和改进这些基础算法，以适应各种复杂的场景。