头歌Java算法与数据结构测试——插入排序
时间: 2023-07-25 21:13:23 浏览: 111
好的,我很乐意回答你关于插入排序的问题。插入排序是一种简单直观的排序算法,它的基本思想是将一个数据序列分为已排序和未排序两部分,每次从未排序的部分选取一个元素插入到已排序的部分中,使得插入后仍保持有序。以下是插入排序的Java代码实现:
```
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// 逐个比较已排序部分中的元素,找到插入位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
```
在这段代码中,我们首先定义了一个数组 `arr`,然后使用 `n` 表示数组长度。我们使用一个循环,从第二个元素开始遍历数组,因为第一个元素可以认为是已排序的部分。对于每个未排序部分的元素,我们将其存储在变量 `key` 中,然后从已排序部分的末尾开始比较,找到插入位置。我们用一个 while 循环来移动已排序部分中大于 `key` 的元素,并为 `key` 找到正确的插入位置。最后,我们将 `key` 插入到已排序部分中。
插入排序的时间复杂度为 $O(n^2)$,空间复杂度为 $O(1)$。虽然插入排序的时间效率不如快速排序等高级排序算法,但由于其实现简单,常数因子小,对小规模数据的排序效果很好。