Java 中的插入排序116

插入排序是一种简单高效的排序算法，它适用于小规模数据集合或部分有序的数据。它的基本思想是将元素逐个插入到一个有序的序列中，直到所有元素都按顺序排列。

Java 代码

以下 Java 代码实现了插入排序算法：```java
public class InsertionSort {
public static void main(String[] args) {
int[] arr = { 5, 2, 8, 1, 3 };
sort(arr);
for (int i = 0; i < ; i++) {
(arr[i] + " ");
}
}
public static void sort(int[] arr) {
for (int i = 1; i < ; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && key < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}
```

算法步骤

插入排序算法按以下步骤工作：1. 初始化：将第一个元素视为有序序列，剩余元素视为无序序列。
2. 循环：从第二个元素开始，循环遍历无序序列。
3. 插入：对于每个无序元素，将其与有序序列中的元素比较。
4. 移动：如果无序元素小于当前有序元素，则将有序元素向后移动，直到找到合适的位置。
5. 插入：将无序元素插入到找到的位置。
6. 重复：对无序序列中的所有元素重复步骤 3-5。

时间复杂度

插入排序的时间复杂度为 O(n^2)，其中 n 是数组中元素的数量。这是因为算法必须遍历数组两次：一次寻找合适的位置，一次移动元素。

虽然插入排序的时间复杂度较高，但它在以下情况下非常有效：* 小数据集：对于小数据集，插入排序比其他排序算法更快。
* 部分有序数据集：如果数据集已经部分有序，则插入排序可以比其他排序算法更快。

优点和缺点优点：
* 简单易于实现
* 对小数据集有效
* 对部分有序数据集有效
* 稳定（即，不改变相等元素的相对顺序）
缺点：
* 时间复杂度为 O(n^2)
* 随着数据集大小的增加，效率降低

2024-12-08

上一篇：Java 中的数据类型输出

下一篇：《Java 飞机大战 源代码深度解析》