插入排序：原理、实现与分析（图文详解）

插入排序：原理、实现与分析（图文详解）

引用

CSDN

1.

https://blog.csdn.net/2302_80220709/article/details/142306263

插入排序是一种简单直观的排序算法，其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。本文将详细介绍插入排序的算法思想、实现步骤、复杂度分析以及应用场景。

一、插入排序 算法思想

插入排序(Insert Sort)是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。它的思想类似于我们打扑克牌时的整理。

二、插入排序 算法步骤

1. 将第一待排序 序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从尾到头依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

具体步骤是这样的：

（以排升序为例）

• 从第一个元素开始，该元素可以认为已经被排序。
• 取出下一个元素，在已经排序的元素序列中从后向前扫描。
• 如果该元素（已排序）大于新元素，将该元素向后移动一位。
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
• 将新元素插入到该位置后。
• 重复步骤2~5，直到所有元素都排序完成。

三、C语言代码实现

//插入排序
void InsertSort(int* a, int len)
{
    //0到end有序，插入a[end+1]
    for (int i = 0; i < len - 1; i++)
    {
        int end = i;
        int tmp = a[i + 1];
        while (end >= 0)
        {
            if (a[end]>tmp)
            {
                a[end + 1] = a[end];
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

四、复杂度分析

时间复杂度：O(n^2)

• 最好情况（O(n)）：当输入数组已经是排序状态时，插入排序的性能最优。此时，每个元素只需与其前面的一个元素进行比较（因为它已经位于正确的位置），因此总共需要进行大约n-1次比较，时间复杂度为O(n)。这里的n是数组的长度。
• **最坏情况（O(n^2)）：**当输入数组完全逆序时，插入排序的性能最差。对于每个元素，都需要与其前面的所有元素进行比较，直到找到合适的位置。因此，第i个元素需要比较i次（其中i从2开始，直到n），总共需要进行的比较次数大约为1 + 2 + 3 + ... + (n-1) = n(n-1)/2，时间复杂度为O(n^2)。
• **平均情况（O(n^2)）：**对于随机排列的数组，插入排序的平均时间复杂度也是O(n^2)。这是因为大部分情况下，元素都需要进行多次移动和比较才能找到正确的位置。

空间复杂度：O(1)

插入排序是一种原地排序算法，它只需要一个额外的存储空间来暂存当前需要插入的元素（即“key”），而不需要额外的数组来存储排序过程中的数据。因此，其空间复杂度为O(1)。

稳定性：稳定算法

插入排序是一种稳定的排序算法。在插入排序过程中，如果两个相等的元素，后面的元素不会移动到前面元素的前面，而是直接插入到与它相等的元素之后，从而保持了原有的相对顺序。

五、应用场景

插入排序虽然在大规模数据集上可能不是最高效的排序算法，但其简单性、稳定性和在某些特定场景下的高效性使得它在许多实际应用中仍然具有一定的价值。

• 小规模数据集：由于插入排序在小规模数据集上表现良好，且实现简单，因此常用于对少量数据进行排序的场景。
• 快速排序的小区间优化：
• 几乎有序的数据集：当数据已经接近有序时，插入排序的性能会显著提高。因为此时大部分元素已经处于或接近其最终位置，所需的比较和移动次数会大幅减少。
• 链表排序：由于链表不支持像数组那样的随机访问，因此在链表上进行排序时，插入排序成为了一个非常合适的选择。它可以通过改变节点的指针来实现元素的移动，而不需要额外的存储空间。