DSA 选择排序时间复杂度

有关时间复杂度的通用解释，请参阅此页面。

选择排序时间复杂度

选择排序算法 遍历数组中的所有元素，找到最小值，并将其移动到数组的开头，然后一遍又一遍地重复此操作，直到数组排序完成。

选择排序会遍历一个包含 \(n\) 个值的数组 \(n-1\) 次。这是因为当算法只剩下最后一个值未排序时，最后一个值也必然已在其正确的位置。

算法第一次遍历数组时，会比较所有值以找出哪个是最小的。

算法第二次遍历数组时，会比较除第一个值之外的所有值以找出哪个是最小的。

就这样，数组中未排序的部分越来越短，直到排序完成。因此，平均而言，当算法遍历数组以查找最小值并将其移动到数组开头时，会考虑 \(\frac{n}{2}\) 个元素。

除了所有需要的比较之外，需要的交换次数为 \(n \)。

我们可以开始计算选择排序算法的操作次数

\[ \begin{equation} \begin{aligned} 操作次数 {} & = (n-1)\cdot \frac{n}{2} + n \\ & = \frac{n^2}{2} - \frac{n}{2} + n \\ & = \frac{n^2}{2} + \frac{n}{2} \end{aligned} \end{equation} \]

在考虑算法的运行时间时，我们关注非常大的数据集，这意味着 \(n\) 是一个非常大的数字。对于非常大的数字 \(n\)，\(\frac{n^2}{2}\) 项比 \(\frac{n}{2}\) 项大得多，我们可以通过简单地去掉第二项 \(\frac{n}{2}\) 来近似。

\[操作次数 = \frac{n^2}{2} + \frac{n}{2} \approx \frac{n^2}{2} = \frac{1}{2} \cdot n^2 \]

使用大 O 表示法来描述选择排序算法的时间复杂度，我们得到

\[ O( \frac{1}{2} \cdot n^2) = \underline{\underline{O(n^2)}} \]

选择排序算法的时间复杂度可以用这样的图表显示

正如您所见，运行时间与冒泡排序相同：当增加数组大小时，运行时间会迅速增加。

选择排序模拟

运行不同数量值的数组的模拟，并查看选择排序在 \(n\) 个元素的数组上所需的操作次数为 \(O(n^2)\)

与冒泡排序相比，我们在此模拟中注意到的最显著的区别是，选择排序的最佳和最坏情况实际上几乎相同 (\(O(n^2)\))，但对于冒泡排序，最佳情况运行时间仅为 \(O(n)\)。

选择排序在最佳和最坏情况下的主要区别在于交换次数。在最佳情况下，选择排序无需交换任何值，因为数组已排序。而在最坏情况下，数组已排序但顺序错误，因此选择排序必须进行与数组中值数量相同的交换。