织梦做泰文网站,新网备案成功了怎么做网站,知名高端网站设计企业,网站开发公司 重庆插入排序#xff08;Insertion Sort#xff09;
插入排序是一种简单的排序算法。它的基本思想是#xff1a;将数组分为已排序部分和未排序部分#xff0c;然后逐个将未排序部分的元素插入到已排序部分的正确位置。插入排序类似于整理扑克牌的过程。
插入排序的步骤#…插入排序Insertion Sort
插入排序是一种简单的排序算法。它的基本思想是将数组分为已排序部分和未排序部分然后逐个将未排序部分的元素插入到已排序部分的正确位置。插入排序类似于整理扑克牌的过程。
插入排序的步骤
初始化将第一个元素视为已排序部分。插入元素从未排序部分取出一个元素将其插入到已排序部分的正确位置。重复过程重复上述步骤直到所有元素都被排序。
时间复杂度
最坏情况O(n²) —— 当数组是逆序的时候。最好情况O(n) —— 当数组已经有序的时候。平均情况O(n²)
空间复杂度
O(1) —— 插入排序是一种原地排序算法不需要额外的存储空间。 Python 实现
def insertion_sort(arr):n len(arr)for i in range(1, n):key arr[i] # 当前需要插入的元素j i - 1# 将比 key 大的元素向后移动while j 0 and arr[j] key:arr[j 1] arr[j]j - 1# 将 key 插入到正确位置arr[j 1] keyreturn arr# 示例使用
arr [12, 11, 13, 5, 6]
sorted_arr insertion_sort(arr)
print(排序后的数组:, sorted_arr)输出结果
排序后的数组: [5, 6, 11, 12, 13]插入排序的详细过程
以数组 [12, 11, 13, 5, 6] 为例 第一轮 已排序部分[12]未排序部分[11, 13, 5, 6]将 11 插入到已排序部分数组变为 [11, 12, 13, 5, 6]。 第二轮 已排序部分[11, 12]未排序部分[13, 5, 6]将 13 插入到已排序部分数组变为 [11, 12, 13, 5, 6]。 第三轮 已排序部分[11, 12, 13]未排序部分[5, 6]将 5 插入到已排序部分数组变为 [5, 11, 12, 13, 6]。 第四轮 已排序部分[5, 11, 12, 13]未排序部分[6]将 6 插入到已排序部分数组变为 [5, 6, 11, 12, 13]。 排序完成。 插入排序的优缺点
优点
实现简单易于理解。对于小规模数据或基本有序的数据效率较高。是稳定的排序算法相同元素的相对位置不变。
缺点
时间复杂度较高不适合处理大规模数据。对于逆序数据性能较差。 插入排序的适用场景
数据规模较小。数据基本有序。需要稳定排序的场景。
