插入排序
思路：
就是将没有排序的元素逐步地插入到已经排好序的元素后面，保持元素的有序
视频的实现过程如下：
插入排序全过程
代码实现过程如下：
public static void Insertion(int[] arr) { for (int i = 1; i < arr.length; i++) { // 从第二个元素开始 int key = arr[i]; // 当前要插入的元素 int j = i - 1; // 已排序部分的最后一个位置 // 将已排序部分大于key的元素向右移 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 向右移动元素 j--; // 继续往左移动 } // 将key插入到正确的位置 arr[j + 1] = key; }
}
时间复杂度：
插入排序的时间复杂度其实分为最坏情况、最好情况和平均情况，
1. 最坏情况（Worst Case）：
最坏的情况发生在数组是逆序的情况下。也就是说，数组中的每一个元素都比它前面的元素大。
- 假设我们有一个数组
[5, 4, 3, 2, 1]，它完全是逆序的。 - 对于每个元素，插入排序都需要将它和前面所有的元素比较，直到它被插入到最前面。
对于第一个元素，已经是排序好了的，所以不需要比较。
- 对第二个元素，
4，需要比较一次（和5比较），然后把它插入到第一个位置。 - 对第三个元素，
3，需要和前面的5和4都比较，再把它插入到第三个位置。 - 对第四个元素，
2，需要和前面的三个元素5、4、3都比较，再插入到第四个位置。 - 对最后一个元素，
1，需要和前面所有四个元素比较，再插入到最前面。
这种情况，每个元素的比较次数逐渐增多，总的比较次数大约是：
- 第一个元素比较 0 次
- 第二个元素比较 1 次
- 第三个元素比较 2 次
- …
- 第n个元素比较 n-1 次
因此，比较的总次数是：
[
0 + 1 + 2 + … + (n-1) = \frac{n(n-1)}{2}
]
这就是二次方的增长，所以最坏情况下的时间复杂度是：O(n^2)。
2. 最好情况（Best Case）：
最好情况发生在数组本身已经是有序的情况下。即所有的元素已经在正确的位置，不需要任何交换。
- 假设我们有一个数组
[1, 2, 3, 4, 5]。 - 对于每一个元素，它已经在排序好的部分中，所以每次插入时都只需要比较一次，发现它的位置已经正确，无需做交换。
所以对于每个元素，只需要进行一次比较，总的时间复杂度就是O(n)，即线性时间。
3. 平均情况（Average Case）：
平均情况就是假设数据是随机的，每个元素大约需要和一半的已排序部分比较。
每个元素平均需要比较 n/2 次。因为是随机的情况，所以比较的次数大致是：
[
\frac{n}{2} \times n = O(n^2)
]
所以，平均情况下，插入排序的时间复杂度也是O(n^2)。
总结：
- 最坏情况：O(n^2)（数组逆序时）
- 最好情况：O(n)（数组已排序时）
- 平均情况：O(n^2)（随机排列的情况）
因此，虽然插入排序在最好的情况下效率较高，但在大多数情况下，它的时间复杂度是 O(n^2)，这使得它在处理大规模数据时不太高效。
如果数组已经基本排好序或者只有少量元素需要调整，插入排序还是一个不错的选择，因为它的空间复杂度是 O(1)，即它不需要额外的空间来存储临时数据。
