插入排序

概念

插入排序（Insertion Sort）是一种简单直观的排序算法，其基本思想是将待排序的数组分成已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置，使得已排序部分仍然保持有序。

插入排序的具体步骤如下：

将数组视为已排序和未排序两部分，初始时已排序部分只包含第一个元素，未排序部分包含剩余的元素。
从未排序部分依次取出一个元素，将其插入到已排序部分的适当位置，使得已排序部分仍然保持有序。
重复步骤2，直到所有元素都插入到已排序部分。

插入排序可以使用两种方式实现：一种是从前往后逐个遍历未排序部分，逐步将其插入到已排序部分中；另一种是从后往前遍历已排序部分，找到插入位置后再进行插入操作。

插入排序的时间复杂度为O(n^2)，其中n是待排序数组的长度。在实际应用中，插入排序在处理部分已排序的数据时性能较好，因为在这种情况下，插入操作的次数较少，排序效率较高。插入排序是一种稳定的排序算法，适用于小规模数据或部分已排序的数据。

优缺点

插入排序优点和缺点如下：

优点：

简单直观：插入排序是一种非常简单直观的排序算法，易于理解和实现，适用于初学者学习排序算法的入门。
稳定性：在实现过程中，插入排序是稳定的排序算法，即相同元素的相对位置不会改变。这意味着如果待排序数组中存在相同元素，排序后它们的相对顺序仍然保持不变。
部分有序数据的高效性：对于部分有序的数据，插入排序的性能较好。因为在部分有序的情况下，插入操作的次数较少，排序效率较高。

缺点：

效率较低：插入排序的时间复杂度为O(n^2)，其中n是待排序数组的长度。在大规模数据的情况下，效率较低，性能不如一些其他排序算法，如快速排序、归并排序等。
不适用于大规模数据：由于插入排序的时间复杂度较高，不适用于大规模数据的排序。当数据规模较大时，选择其他更加高效的排序算法可能会更合适。
不适用于链表：插入排序的思想是在数组中移动元素来为插入元素腾出空间，因此对于链表等非连续存储结构，插入排序的效率较低，不适用于链表的排序。

代码实现

func InsertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        key := arr[i] // 当前待插入的元素
        j := i - 1    // 已排序部分的最后一个元素的索引

        // 将比当前元素大的元素后移一位
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }

        // 将当前元素插入到合适位置
        arr[j+1] = key
    }
}

总结

插入排序：依次从未排序序列取出一个元素插入已排序序列的合适位置。

复杂度：

平均时间复杂度：O(n²)
最坏时间复杂度：O(n²)
最优时间复杂度：O(n)
空间复杂度：O(1)

参考：插入排序-维基百科

插入排序 ​

概念 ​

优缺点 ​

代码实现 ​

总结 ​

插入排序

概念

优缺点

代码实现

总结