数据结构与算法-插入排序

引言

        在计算机科学领域，数据结构和算法是理解和优化程序性能的关键。其中，排序算法是众多算法中不可或缺的一部分。今天我们将聚焦于一种直观且易于理解的排序算法——插入排序，并对其内在原理、实现步骤以及实际应用中的优缺点进行深入探讨。

一、什么是插入排序？

        插入排序(Insertion Sort) 是一种简单直观的排序方法，它的工作原理类似于我们手动整理一副扑克牌的过程。插入排序将待排序序列看作是一个有序序列和一个无序序列的组合，每次从无序序列中取出一个元素，通过比较找到其在有序序列中的合适位置并插入，直到所有元素都排好序。

二、插入排序详细步骤

1. 初始化：将数组的第一个元素视为已排序序列（长度为1），后续元素视作未排序序列。

2. 取值与比较：从未排序序列中取出第一个元素，与已排序序列中的元素从后往前逐个比较。

3. 插入操作：若当前元素比已排序序列中的某个元素小，则将该元素及之后的所有元素依次向后移动一位，然后将当前元素插入到对应的位置上。

4. 重复执行：继续从未排序序列中取出下一个元素，重复上述比较和插入过程，直至所有元素都被处理过。

三、插入排序的时间复杂度与空间复杂度分析

• 时间复杂度：在最好的情况下（即输入数组已经是有序的），插入排序只需要进行n-1次比较，时间复杂度为O(n)。但在最坏的情况下（即输入数组是逆序的），需要进行的比较次数为n(n-1)/2，时间复杂度为O(n²)。

• 空间复杂度：由于插入排序是原地排序算法，不需要额外的存储空间，因此其空间复杂度为O(1)。

四、插入排序的优缺点

优点

• 对于近乎有序的小规模数据集，插入排序效率较高。
• 算法实现简单，逻辑清晰，易于理解。
• 不需要额外的存储空间，适合内存资源有限的情况。

缺点

• 当面对大规模或者无序的数据时，插入排序效率较低，因为其时间复杂度为O(n²)，不适合大数据排序。
• 插入排序在进行元素移动时会产生较多的交换操作，对缓存不友好，可能影响性能。

五、插入排序的图解过程 

图解小结 

        插入排序的基本思想就是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把他的排序码依次与有序表元素的排序码进行比较，将他插入到有序表中合适位置，使之成为新的有序表。

六、插入排序的代码实践  

1.展示每一次选择排序过程

        int insertVal;
        int insertIndex;
 
        //给第二个数找位置
        insertVal = arr[1];
        insertIndex = 1 - 1;
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
//        退出循环以及给第二个数找到合适位置
        arr[insertIndex + 1] = insertVal;
        System.out.println("第一轮插入的数");
        System.out.println(Arrays.toString(arr));
 
        //给第三个数找位置
        insertVal = arr[2];
        insertIndex = 2 - 1;
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
//        退出循环以及给第二个数找到合适位置
        arr[insertIndex + 1] = insertVal;
        System.out.println("第二轮插入的数");
        System.out.println(Arrays.toString(arr));

2.总结规律得到过程  

    //    有规律可知
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex + 1] = insertVal;
            System.out.printf("第%d轮排序为", i);
            System.out.println(Arrays.toString(arr));
        }
    }

七、总结

        尽管在大规模数据排序场景下插入排序显得力有不逮，但在某些特定条件下，插入排序仍具有较高的实用价值。例如，在部分稳定排序要求的场景下，插入排序因其稳定的特性而被选用；另外，在数据规模较小或数据已经局部有序的情况下，插入排序的表现往往优于其他复杂的排序算法。

        插入排序虽然不是最高效的排序算法，但它在理解排序原理、熟悉基本编程操作等方面有着不可替代的作用。掌握插入排序不仅能帮助我们更好地理解更高级排序算法的设计思路，也能在实际开发中根据具体场景灵活选择最适合的排序策略。