插入排序

zzz

插入排序是一种简单直观的排序算法，适用于小规模数据的排序。它的基本思想是将待排序数组分为已排序和未排序两部分，然后通过将未排序部分的元素逐个插入到已排序部分的合适位置来实现排序。
算法步骤

• 初始化：将第一个元素视为已排序的部分，第二个元素视为未排序的部分。
• 从未排序部分取出元素：依次选择未排序部分的第一个元素。
• 插入到已排序部分：
  
  • 从已排序部分的末尾开始，与当前元素进行比较，找到合适的位置将其插入。
  • 为了插入该元素，需要将比它大的元素向后移动一位。
    
• 重复：不断重复步骤2和3，直到所有元素都被插入到已排序部分中。
  

示例考虑数组：[5, 2, 9, 1, 5, 6]，使用插入排序进行排序的过程如下：

• 初始状态：[5 | 2, 9, 1, 5, 6]
• 插入 2：
  
  • 2 < 5，移动5，插入位置为开头：[2, 5 | 9, 1, 5, 6]
    
• 插入 9：因为9大于5，保持不变：[2, 5, 9 | 1, 5, 6]
• 插入 1：
  
  • 1 < 9，移动9。
  • 1 < 5，移动5。
  • 1 < 2，移动2，插入1为：[1, 2, 5, 9 | 5, 6]
    
• 插入 5：
  
  • 5 >= 5，保持在当前位置：[1, 2, 5, 5, 9 | 6]
    
• 插入 6：
  
  • 6 < 9，移动9，插入6为：[1, 2, 5, 5, 6, 9]
    

最终得到排序后的数组：[1, 2, 5, 5, 6, 9]
特点

• 时间复杂度：
  
  • 最坏情况下（数组逆序）是 (O(n^2))。
  • 平均情况下是 (O(n^2))。
  • 最优情况下（数组已排序）是 (O(n))。
    
• 空间复杂度：(O(1))（原地排序）。
• 稳定性：插入排序是稳定的，相等元素的相对顺序不会改变。
  

应用场景

• 适合小规模数据的排序。
• 当数据集基本有序时，可以非常高效。
• 在一些复杂的排序算法（如快速排序）中作为基础排序方法使用。
  

如果你想要具体的代码实现或有其他相关问题，欢迎随时询问！