比较速度与数组中复制的速度

Question

我一直在比较选择和插入排序。据我所知，插入排序作用于倒置计数，而不是依赖于它。但在最坏的情况下，总的反转计数将是最大的，并且在插入排序中，交换的数目将是最大/大于选择排序，因为在选择排序中，总交换总是输入大小'n‘的顺序，并且不大于该顺序，并且它将比插入排序中小得多。

在最坏的情况下，时间复杂度将取决于比较的数量(在选择排序的情况下等于或更少)和交换的数量(在插入排序中更多)。因此，如果交换/写入更快，我可以使用插入排序，但如果与比较相比写入成本较高，则我将使用选择排序。那么，哪种排序算法在最坏的情况下会更好，如果我使用数组作为数据结构，如何决定比较速度更快或复制速度更快。

Answer 1

对于插入排序和选择排序，最坏情况下的比较数是相同的，即O(nxn)。然而，需要注意的关键是：

选择排序中的比较次数始终为O(nxn)，而：

插入排序中的比较次数在最佳情况下为O(n)。最好的情况是数据已经排序。

因此，如果比较次数是衡量性能的标准，则使用进行插入排序。

然而，还需要注意的是：

对于最坏的情况，选择排序中的交换数量是O(n)。而：

在最坏的情况下，插入排序中的交换数量可以达到O(nxn)。

因此，如果交换的数量是衡量性能的标准，则选择。