对于几乎排序的文件、插入或选择排序，您会使用哪一种？

Question

我想知道您是否会使用插入或选择一个几乎排序的文件。这两家公司平均进行了多少次互换？我听说过用于选择的N/2和O(n)！我知道插入时必须扫描数组的排序部分，以查找放置新元素的位置，但在选择中，必须扫描数组的整个未排序部分，以找到要添加到未排序子数组开头的下一个元素。

Answer 1

有许多流行的排序算法是为了利用几乎排序的数据而设计的。最受欢迎的可能是时间排序，它以Tim的名字命名，他是Python开发人员，他首先提出并实现了作为Python中使用的默认排序算法的算法。在Java的许多版本中，排序算法现在也被用作默认排序算法。

Timsort是一种混合稳定排序算法，它是从合并排序和插入排序派生而来的，它能很好地处理各种真实世界的数据。..。该算法查找已经排序的数据的子序列，并利用这些知识对剩余数据进行更有效的排序。这是通过将已识别的子序列(称为run )与现有运行合并来完成的，直到满足某些条件为止。..。

当数据几乎按近似排序的意义排序时，插入排序是非常有效的：

当输入中的每个元素离其排序位置维基百科不超过k个位置时，时间复杂度为O(nk)。

插入排序不能利用数据几乎被排序的许多其他常见情况，例如倒序，或者数据由两次排序数据组成(例如，从连接两个排序数组的结果)。

选择排序并不能真正受益于几乎已排序的数据。所以，如果你知道你的数据中有一些近似的排序，那么这是一个糟糕的算法选择。

Answer 2

在选择排序和插入排序的比较中，选择排序在\Theta(n^2)中工作，并比较列表中的所有值。因此，数组的近似排序无助于在选择排序中进行更快的排序！但是，在插入排序中，最糟糕的情况是O(n^2)和几乎已排序的数组，更改数组的未排序部分，将比在您的情况下选择排序具有更好的性能。

Answer 3

在插入排序中，对于最坏情况下的senarioО(n^2)比较和交换，对于最佳情况O(n)比较，O(1)交换。

在选择排序中，排序和未排序数组没有任何区别，在最佳和最坏的情况下都会消耗n2 (O(n2))的顺序。

因此，对于几乎已排序的文件，插入排序会更好。