设列表的长度为n，反转次数为d . 为什么插入排序在O（n d）时间运行，为什么冒泡不排序？
当我考虑这个问题时，我正在考虑最糟糕的情况 . 由于反转的最坏情况是n（n-1）\ 2，因此气泡和插入排序都在同一时间运行 . 但后来我不知道如何回答这个问题，因为我发现它们是一样的 . 有人可以帮我弄这个吗？
对于冒泡排序，如果最后一个元素需要到达第一个位置（n个反转），则需要在整个数组上循环n次，每次将元素向前移动一个位置，这样你得到n ^ 2步，所以你得到O （N ^ 2）无论d的值如何 .
插入排序中的相同设置将仅执行n n步骤以使所有内容排序（O（N d）） . d实际上是为了使事物排序需要做的交换插入排序的总数 .
当你假设d的最坏情况值是n（n-1）/ 2时你出错了 . 虽然这是真的，如果你想用d来表达复杂性，你不能用它最坏的情况来代替它，除非你没有更高的界限 .
1 回答
对于冒泡排序，如果最后一个元素需要到达第一个位置（n个反转），则需要在整个数组上循环n次，每次将元素向前移动一个位置，这样你得到n ^ 2步，所以你得到O （N ^ 2）无论d的值如何 .
插入排序中的相同设置将仅执行n n步骤以使所有内容排序（O（N d）） . d实际上是为了使事物排序需要做的交换插入排序的总数 .
当你假设d的最坏情况值是n（n-1）/ 2时你出错了 . 虽然这是真的，如果你想用d来表达复杂性，你不能用它最坏的情况来代替它，除非你没有更高的界限 .