插入排序思路
插入排序是一种简单的排序算法，其工作原理如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后，继续重复步骤2~4
时间空间复杂度分析
插入排序的过程分为n-1趟排序，每趟排序需要进行n-i次比较和移动。最好情况下（元素升序有序），只需要进行n-1次比较，无需移动元素，时间复杂度为O(n)。最坏情况下（元素降序有序），需要进行n-1次比较和n-1次移动，时间复杂度为O(n^2)。平均情况下，插入排序的时间复杂度为O(n^2)。
空间复杂度方面，插入排序只需常数级别的额外空间存储临时变量，因此空间复杂度为O(1)。
伪代码
代码语言：javascript复制function insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j 1] = arr[j]
j -= 1
arr[j 1] = key
return arr基于java实现
代码语言：javascript复制public class InsertionSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 1, 4, 6, 9, 2, 7};
insertionSort(arr);
for (int i : arr) {
System.out.print(i " ");
}
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; 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;
}
}
}
执行结果：
1 2 3 4 5 6 7 8 9
- 定义一个名为`InsertionSort`的公共类。
- 在`main`方法中，创建一个整数数组`arr`并初始化。
- 调用`insertionSort`方法对数组进行排序。
- 使用`for`循环遍历排序后的数组，并打印每个元素。
`insertionSort`方法：
1. 使用一个for循环从数组的第二个元素（索引为1）开始遍历。
2. 将当前元素存储在变量`key`中。
3. 初始化一个变量`j`，其值为当前索引减1。
4. 使用一个while循环，当`j`大于等于0且`arr[j]`大于`key`时，将`arr[j]`向右移动一个位置（即将`arr[j]`赋值给`arr[j 1]`），然后将`j`减1。
5. 当while循环结束时，将`key`的值插入到正确的位置（即`arr[j 1]`）。
