直接插入排序的最大比较次数为什么是(n+2)*(n-1)⼀2

2025-06-24 13:54:35
推荐回答(1个)
回答1:

你可以仔细看一下伪代码,首先假设第一个有序,从第二个开始考虑才开始跟前面比,而为了避免向前越界,0下标跟要插入的值相等(更重要的是其他的用途),阻止了向前,实际上每个插入的值如果比所有已插入的值小的话还会跟0(哨兵)比较。