一 插入排序概述
插入排序是稳定的原地排序算法，焦点头脑是徐徐构建有序序列。对于未排序部分的每个元素，在已排序序列中从后向前扫描，找到合适位置插入。时间复杂度为：
最优：O(n)（已有序）
最差：O(n^2)（完全逆序）
均匀：O(n^2)
二 二分查找优化（淘汰比较次数）
1 焦点头脑
在寻找插入位置时，利用二分查找代替次序查找，将比较次数从O(n)降低到O(log n)。
2 实用场景
数据规模较大且比较操纵代价较高（例如复杂对象比较） 。
3 时间复杂度
比较次数O(n log n)，移动次数仍为O(n^2)→ 整体O(n^2)，但常数更小 。
4 c++代码
void insertionSortOptimized(int arr[], int n) {
for (int i = 1; i < n; i++) {
int temp = arr;
int left = 0, right = i - 1;
// 二分查找插入位置
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
