use*_*632 1 sorting swap selection-sort
我相信选择排序有以下行为:
最佳案例:由于所有元素排列正确,因此无需交换
最坏的情况:需要n-1次交换,即每次传递需要交换,并且有n-1次传递,因为我们知道其中n是数组中的元素数量
平均情况:无法找到这个.找到它的程序是什么？
以上信息是否正确？
这表示交换的时间复杂度在最好的情况下是O(n) http://ocw.utm.my/file.php/31/Module/ocwChp5SelectionSort.pdf
选择排序的每次迭代都包括扫描整个数组,找到尚未放置的最小元素,然后将其交换到适当的位置.在一个简单的选择排序实现中,这意味着无论输入数组中的元素分布如何,总会有n - 1个交换.
但是,如果要最小化交换次数,则可以实现选择排序,以便在要移动的元素已经位于正确位置的情况下不执行交换.如果你添加了这个限制,那么你是正确的,在最好的情况下会进行零交换.(我不确定以这种方式修改选择排序是否值得,因为在大多数情况下交换非常快).
真的,这取决于实施.您可能有一个奇怪的选择排序实现,在每次迭代时不断地将候选最小元素交换到其暂定的最终点,这将在最坏的情况下显着增加交换的数量.不过,我不确定你为什么要这样做.这样的小细节说明了为什么你的解释似乎与你在网上找到的东西不一致 - 取决于代码如何放在一起,交换的数量可能不同.