这是选择排序还是插入排序？
假设我们使用二次排序算法对一个由十个整数组成的数组排序。在对算法的主循环进行四次迭代之后，排列数组元素如下所示：
1 2 3 4 5 0 6 7 8 9
哪条语句是正确的？(注意:我们的选择排序首先选择最大的项目。)
A.算法可以是选择排序，也可以是插入排序。
B。算法可能是选择排序，但不能是插入排序。
C.算法可能是插入排序，但不能选择排序。
D算法既不是选择排序，也不是插入排序。
我认为答案应该是A(插入排序和选择排序)？但我在一些网站上发现正确答案是C。我不知道原因。谁能解释一下。
如果我错了，请纠正我。
来源：谷歌图书
回答 4
Stack Overflow用户
发布于 2015-05-09 03:53:37
这种输出对于最大的优先选择排序是可能的。
它不能是最小优先选择排序，因为选择排序保持不变，在n次迭代后，列表中的前n项是完全排序的。因此，如果这是一种选择排序，您将期望值为0的元素在第一次迭代中被排序为索引0。因此，在前4次迭代之后，列表将类似于0 1 2 3 ...。
由于插入排序具有不同的不变量，所以最大先插入排序和最小插入排序都可以输出。在插入排序中，经过n次迭代后，列表中的前n项(最后n项表示最大的第一次排序)是按彼此排序的，但它们不一定在列表中的最后位置。
对于最小的第一个插入排序，经过4次迭代之后，就可以看到“of”0，因为排序还没有迭代到在其正确的索引中重新定位0。
Stack Overflow用户
发布于 2015-05-09 03:51:07
插入排序是可能的，因为当前快照刚刚完成从索引0到4的数组排序。
选择排序将首先选择最小值(在示例中为0)，并将其放在左侧。所以答案是C。
Stack Overflow用户
发布于 2015-05-09 03:56:01
这可以是最大优先选择排序或插入排序的输出。如果数组最初的样子是这样的，经过两种算法的4次迭代后，它仍然是这样的。它不可能是最小的优先选择排序，因为经过4次迭代之后，数组的前4项将是0 1 2 3。
https://stackoverflow.com/questions/30135705
复制相似问题
腾讯云开发者
