插入排序算法在最坏情况下最多的比较次数是

发布网友 发布时间：2022-04-25 14:57

我来回答

共5个回答

热心网友 时间：2023-10-10 07:45

答案是B
数组【a[0] 4 3 2 1】 3移到a[0] 和a[1]比较一次 a1后移 此时j-- a[0]和a[j]是同一个 比较第二次 退出while循环，所以i从2开始 第一个元素的比较次数是2 也就是i 然后求和 从i等于2开始到n 对i求和 结果为B

热心网友 时间：2023-10-10 07:45

设有n个数，最坏的情况是逆序（假设要排成顺序）
则，第j个数（j=2.....n)需要和前面的j-1个数比较，那么最终结果为
1+2+3+...+n-1
所以答案是A

热心网友 时间：2023-10-10 07:46

第i个数与前i-1个数继续比较，最坏一共比较i-1次。最后还会与最前面设置的哨兵比较一次，加上1。
所以第i个数比较i次。从i=2的位置开始求和。
最后结果是b

热心网友 时间：2023-10-10 07:46

有n个数，最坏情况是B

热心网友 时间：2023-10-10 07:47

A.

你可以试试用插入排序算法，将一个顺序的数组，排序为一个逆序的数组，看看它要循环多少次。