插入排序

基本概念

插入排序（Insertion Sort）基本思想：

将数组分为有序区间和无序区间，每次从无序区间取出一个元素插入到有序区间的正确位置。

算法步骤

假设数组长度为 n，算法步骤如下：

初始化：有序区间为 $[0,0]$ ，无序区间为 $[1,n−1]$
第i趟插入（i 从 11 到 n−1）：
- 取出无序区间第一个元素 $nums[i]$
- 从右到左遍历有序区间，将大于 $nums[i]$ 的元素右移一位
- 找到合适位置后插入 $nums[i]$
- 有序区间扩展为 $[0,i]$ ，无序区间变为 $[i+1,n−1]$

内部实现：

class Solution:
	def insertionSort(self,nums:[int])->[int]:
		for i in range(i,len(nums)):
			temp=nums[i]
			j=i
			while j>0 and nums[j-1]>temp:
				nums[j]=nums[j-1]
				j-=1
			nums[j]=temp
		return nums
	def sortArray(self,nums:[int])->[int]:
		return self.insertionSort(nums)

复杂度分析：

指标	复杂度	说明
最佳时间复杂度	$O(n)$	数组已有序，每个元素只需比较一次
最坏时间复杂度	$O(n^2)$	数组逆序，每个元素需要比较 i−1i−1 次
平均时间复杂度	$O(n^2)$	一般情况下的复杂度
空间复杂度	$O(1)$	原地排序，只使用常数空间
稳定性	稳定	相等元素相对位置不变
适用场景：

数据量较小（n<50）
数据基本有序
在线排序（数据逐个到达）
插入排序是一种简单直观的排序算法，通过逐步构建有序序列实现排序。
优点：实现简单，稳定排序，空间复杂度低，对基本有序数据效率高
缺点：时间复杂度高，不适合大规模数据

插入排序

基本概念

算法步骤

内部实现：

复杂度分析：

应用场景：