Java 插入排序

插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。Java作为一种广泛应用的编程语言，其丰富的类库和强大的功能使得实现插入排序变得相对简单。在Java中，我们可以创建一个名为`InsertionSort`的类来实现插入排序。 以下是一个简单的`InsertionSort`类的实现，它接受一个整型数组作为参数，并对其进行插入排序： ```java public class InsertionSort { public void sort(int[] array) { if (array == null || array.length <= 1) { return; } for (int i = 1; i < array.length; i++) { int key = array[i]; int j = i - 1; // 将比key大的元素向后移动 while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j--; } // 将key插入到正确的位置 array[j + 1] = key; } } } ``` 在这个类中，`sort`方法是主要的操作函数。首先检查输入数组是否为空或长度小于等于1，如果是，则无需排序。接着，我们遍历数组中的每个元素，将当前元素（key）与前面已排序的元素依次比较。如果当前元素小于前面的元素，就将前面的元素向后移动一位，为key腾出位置。当找到合适的位置时，将key插入到数组中。这个过程会持续到所有元素都找到它们的正确位置，从而完成排序。 插入排序的时间复杂度在最坏情况下为O(n^2)，最好情况（已排序数组）为O(n)，平均情况为O(n^2)。由于插入排序每次只与前面的元素比较，所以它对于部分有序的数组表现较好。然而，对于大规模无序数据，插入排序的效率相对较低，更适合小规模或者基本有序的数据。 在实际应用中，Java提供了`Arrays.sort()`方法，它底层使用了更高效的排序算法，如快速排序、归并排序等，适用于大多数场景。但在教学或学习排序算法时，自己实现插入排序可以帮助理解排序算法的基本原理和工作流程。 总结一下，Java插入排序是通过创建一个`InsertionSort`类，定义一个`sort`方法，对给定的一维整型数组进行逐个元素的比较和移动，从而达到排序的目的。这种方法直观易懂，但效率较低，适合于小规模或基本有序的数据。在实际编程中，我们通常会利用Java内置的高效排序方法，如`Arrays.sort()`。