performance - 最昂贵的分拣操作

Question

任何排序算法中最昂贵的操作是什么？是交换操作还是比较操作？

我认为它是交换，但我的朋友认为它是比较。我可以证明比较是成本更高的操作的唯一方法是每个元素都需要比较，但不是每个元素都需要交换（即，如果元素已经在正确的位置，则不必交换）。因此，总体而言，与少数昂贵的互换相比，便宜的比较更多。但我不确定答案。有什么想法吗？

Answer 1

假设一切都在 RAM 中完成，那么交换操作比比较操作要快得多。（这很明显，2 次读取然后是 cpu 操作与 2 次读取、2 次写入以及介于两者之间的所有内容，包括注册表操作）。

这显然取决于您的排序算法，有些比较少，因为元素较少，但交换比较频繁。

采用快速排序，它几乎不会进行比较，然后交换几乎所有内容，以及一个更简单的算法，如冒泡排序，将所有元素相互比较，然后减少交换频率。这也取决于基本数组，如果所有内容都已接近排序，则冒泡排序不会交换任何内容，但仍会比较所有内容，而堆排序（例如）仍然必须“交换”所有内容。

最后，（交换操作的平均数量）（交换操作的时间成本）/（comp 操作的平均数量）（comp 操作的时间成本）对于一个算法来说是相当难以估计的，而且要外推到所有的算法。

我个人认为，任何排序算法的总交换成本总是高于比较成本，但我无法用任何证据支持这一说法（这只是个人见解）。