直接插入排序算法

直接插入排序是一种简单直观的排序算法，它的工作原理与人们打扑克牌时整理手牌的过程非常相似。当你摸到一张新的牌时，你会将它与你手中已经排序好的牌进行比较，找到合适的位置后插入，以保持整个手牌的顺序。这种排序算法的基本思想就是，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

一、算法原理

直接插入排序算法主要分为以下几个步骤：

1. 初始化：将序列的第一个元素视为一个已排序的序列，剩下的元素作为未排序的序列。
2. 逐个处理：从未排序的序列中取出一个元素，在已排序的序列中从后向前扫描。
3. 寻找位置：在已排序的序列中找到该元素应该插入的位置。这一步通过比较来实现，如果已排序的元素大于新元素，则将该元素向后移动一位，为新元素腾出空间。
4. 插入元素：将新元素插入到已排序序列中的正确位置。
5. 重复步骤：重复步骤2至4，直到未排序的序列为空。

二、算法流程

以数组 [4, 2, 5, 1, 3] 为例，详细说明直接插入排序的过程：

1. 初始状态：
   • 已排序序列：[4]
   • 未排序序列：[2, 5, 1, 3]
2. 第一轮：
   • 取出未排序序列的第一个元素 2，与已排序序列 [4] 中的元素进行比较。
   • 发现 4 大于 2，因此将 4 向后移动一位，腾出位置给 2。
   • 插入 2 到已排序序列中，得到新的已排序序列 [2, 4]，未排序序列变为 [5, 1, 3]。
3. 第二轮：
   • 取出未排序序列的第一个元素 5，与已排序序列 [2, 4] 中的元素进行比较。
   • 5 大于 4 和 2，因此直接插入到已排序序列的末尾。
   • 得到新的已排序序列 [2, 4, 5]，未排序序列变为 [1, 3]。
4. 第三轮：
   • 取出未排序序列的第一个元素 1，与已排序序列 [2, 4, 5] 中的元素进行比较。
   • 1 小于 2，因此将 2 及其之后的元素都向后移动一位。
   • 插入 1 到已排序序列中，得到新的已排序序列 [1, 2, 4, 5]，未排序序列变为 [3]。
5. 第四轮：
   • 取出未排序序列的最后一个元素 3，与已排序序列 [1, 2, 4, 5] 中的元素进行比较。
   • 3 小于 4、5，但大于 2，因此将 4 和 5 向后移动一位。
   • 插入 3 到已排序序列中，得到最终的已排序序列 [1, 2, 3, 4, 5]。

三、代码实现

下面是直接插入排序的Java代码实现：

public class InsertionSort {  
    public static void insertionSort(int[] array) {  
        // 遍历未排序的序列  
        for (int i = 1; i < array.length; i++) {  
            // 保存当前要插入的元素  
            int key = array[i];  
            // 已排序序列的最后一个元素的索引  
            int j = i - 1;  
  
            // 将比key大的元素向后移动一位  
            while (j >= 0 && array[j] > key) {  
                array[j + 1] = array[j];  
                j--;  
            }  
            // 插入key到正确的位置  
            array[j + 1] = key;  
        }  
    }  
  
    public static void main(String[] args) {  
        int[] array = {4, 2, 5, 1, 3};  
        insertionSort(array);  
        for (int value : array) {  
            System.out.print(value + " ");  
        }  
    }  
}

四、性能分析

1. 时间复杂度

• 最好情况：当输入数组已经是排序好的情况下，每次循环只需比较一次就能确定位置，此时的时间复杂度为O(n)。
• 平均情况和最坏情况：在大部分情况下，特别是输入数组随机时，每个元素都可能需要比较并移动多次。平均和最坏情况下，每个元素都可能需要与其前面的所有元素进行比较，因此时间复杂度为O(n^2)。

2. 空间复杂度

直接插入排序算法是一个原地排序算法，它只需要使用常量的额外空间来存储临时变量，因此空间复杂度为O(1)。

3. 稳定性

直接插入排序是稳定的排序算法。在排序过程中，相等元素的相对位置不会发生改变。这是因为在比较过程中，一旦找到一个大于或等于待插入元素的元素，就停止比较并插入，不会影响到相同元素的原始顺序。

五、应用场景

尽管直接插入排序在最坏情况下的时间复杂度较高，但它在实际应用中仍有一定的优势：

• 小数据集：对于小规模的数据集，直接插入排序的效率是相当高的，因为其实现简单且不需要额外的存储空间。
• 几乎排序的数据：如果数据已经基本有序，那么直接插入排序的性能会非常好，因为此时元素的移动次数会大大减少。
• 链表排序：对于链表结构的数据，直接插入排序尤其高效，因为链表的插入操作非常迅速，且不需要额外的空间来存储数据。

六、优化与改进

尽管直接插入排序本身已经很高效且简单，但在某些情况下，通过一些优化手段可以进一步提高其性能：

• 二分插入排序：在查找插入位置时，可以使用二分查找算法来减少比较次数，特别是对于大数据集或接近有序的数据集，这种优化效果显著。
• 块排序（TimSort）：Java的Arrays.sort()方法在JDK 7之后采用了TimSort算法，该算法结合了归并排序和直接插入排序的思想，在保持稳定性的同时，能够利用直接插入排序在数据量小时的高效性。

总之，直接插入排序是一种简单直观的排序算法，尽管其时间复杂度在最坏情况下较高，但在特定场景下（如小数据集、几乎排序的数据或链表排序）仍有广泛的应用价值。通过优化和改进，还可以进一步提高其性能。

原文地址：https://blog.csdn.net/weixin_45710581/article/details/142437366

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！