Java 插入排序
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是插入排序的Java实现：
public class InsertionSort { // 插入排序算法实现 public static void insertionSort(int[] array) { int n = array.length; for (int i = 1; i < n; ++i) { int key = array[i]; int j = i - 1; // 将array[i]插入到已排序部分array[0..i-1] while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j = j - 1; } array[j + 1] = key; } } // 打印数组 public static void printArray(int[] array) { int n = array.length; for (int i = 0; i < n; ++i) { System.out.print(array[i] + " "); } System.out.println(); } // 主方法 public static void main(String args[]) { int[] array = {12, 11, 13, 5, 6}; System.out.println("排序前的数组:"); printArray(array); insertionSort(array); System.out.println("排序后的数组:"); printArray(array); }
}代码解释
- 插入排序方法
insertionSort(int[] array):n表示数组的长度。- 外层循环
for (int i = 1; i < n; ++i)遍历数组中的每一个元素，从第二个元素开始（假设第一个元素是已排序的）。 key保存当前要插入的元素array[i]。- 内层循环
while (j >= 0 && array[j] > key)从已排序部分的最后一个元素开始向前扫描，找到key应该插入的位置。 - 如果已排序部分的元素大于
key，则将其向后移动一个位置。 - 最后，将
key插入到正确的位置array[j + 1]。
- 打印数组方法
printArray(int[] array):- 遍历数组并打印每一个元素。
- 主方法
main(String args[]):- 创建一个示例数组。
- 打印排序前的数组。
- 调用
insertionSort方法对数组进行排序。 - 打印排序后的数组。
复杂度分析
- 时间复杂度:
- 平均和最坏情况：O(n^2)，其中
n是数组的长度。 - 最好情况：O(n)，当数组已经是有序的时候。
- 平均和最坏情况：O(n^2)，其中
- 空间复杂度: O(1)，因为排序是原地进行的，不需要额外的存储空间。
插入排序对于小规模数据或部分有序的数据表现良好，但在处理大规模数据时效率较低。