无锡游戏网站建设公司,网站如何建设二级域名代理,网站怎么引蜘蛛,怎么用wordpress建立自己的网站文章目录 插入排序算法实现算法效率分析优化-折半插入排序代码实现对链表进行插入排序小结 插入排序 首先49当作第一个已经排好序得元素#xff0c;将第二个元素与前面得元素对比#xff0c;发现小于49#xff0c;于是49移动位置 此时将65与之前元素对比#xff0c;发现其… 文章目录 插入排序算法实现算法效率分析优化-折半插入排序代码实现对链表进行插入排序小结 插入排序 首先49当作第一个已经排好序得元素将第二个元素与前面得元素对比发现小于49于是49移动位置 此时将65与之前元素对比发现其最大位置不变 97同65处理一样 此时76小于9797移动位置然后再与前面元素比对发现大于此时不动 此时13最小每次与之前元素比对都是小于都会移动位置 此时比对移动直到13才大于 49与之前比对此时大于才移动等于小于都不移动这样保证稳定性
算法实现
此时循环n次每次将第i个元素与前i-1个元素比对如果发现元素大于第i个元素就将该元素右移一位 从一开始存储0当作哨兵当作当前第i个元素
算法效率分析 最好时间复杂度和最坏时间复杂度之和除2来算平均时间复杂度一般和最坏时间复杂度一样
优化-折半插入排序
0位置为前i-1个元素都要比对的元素55发现大于mid此时lowmid1 此时55小于70highmid-1 此时high mid low都相等 接着55小于60lowmid1此时low大于high此时low的元素大于55而high的元素小于55 插入60 此时发现mid60为了保证稳定性此时不会停止 插入90最终low大于high时 插入10最终low大于high时
代码实现
此时相同也要lowmid1 high1low当最后low大于high时
对链表进行插入排序
折半查找对于链表无法实现 比对次数没变
小结
