DSA 选择排序时间复杂度

参见 此页面 了解时间复杂度的基本解释。

选择排序时间复杂度

在 选择排序算法 中，它会遍历数组中的所有元素，找到最小值，并将其移动到数组的开头，并重复此过程，直到数组排序完成。

选择排序会遍历一个包含 \(n\) 个值的数组 \(n-1\) 次。这是因为当算法排序完除最后一个值之外的所有值时，最后一个值也必须在其正确的位置上。

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

算法第二次遍历数组时，会比较每个值，除了第一个值，以找出哪个值最小。

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

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

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

\[ \begin{equation} \begin{aligned} Operations {} & = (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}\) 来近似估计。

\[Operations = \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)\)。

选择排序的最佳情况和最坏情况之间的差异主要是交换次数。在最佳情况下，选择排序不需要交换任何值，因为数组已经排序。在最坏情况下，数组已经排序，但顺序错误，因此选择排序必须执行与数组中的值一样多的交换。