排序算法之插入排序篇

插入排序

思路：

就是将没有排序的元素逐步地插入到已经排好序的元素后面，保持元素的有序

视频的实现过程如下：

代码实现过程如下：

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)，即它不需要额外的空间来存储临时数据。