Number of Comparisons in Straight Selection Sort

1. 概述

在这篇教程中，我们将确定直选排序算法在对输入数组进行升序排序时所进行的比较次数。

2. 问题陈述

我们有一个包含 个元素的输入数组 , 元素可以是任意类型：整数、浮点数、字符串或更复杂的对象。我们的目标是确定直选排序算法将进行多少次比较来对输入数组进行升序排序。结果同样适用于降序排列。

2.1. 直选排序

直选排序算法在每次遍历数组 的第 次时，会寻找从 中的最小元素，并将其放置在数组的第 个位置。在第 次遍历结束时，算法会记住最小元素的索引，并在数组的第 个位置与最小元素交换。以下是伪代码：

在外部循环的第一次迭代中，只有 不与其他元素进行比较。对于每个 ，都会进行一次比较。因此，在第一次外部迭代中，算法总共进行了 次比较。

类似地，在第二次外部迭代中进行 次比较，在第三次迭代中进行 次比较，以此类推，直到第 次遍历。由于数组中有 个元素，没有其他元素可以与 进行比较。因此，在最终迭代中没有进行比较。

从这里我们可以看到，在第 次外部循环的第 次迭代中，直选排序算法会进行 次比较。因此，总比较次数为：

(1) (\sum_{i=1}^{n}(n-i) = (n-1) + (n-2) + \ldots + 2 + 1 + 0 = \sum_{i=0}^{n-1}i = \frac{n(n-1)}{2} \in O(n^2))

无论输入数组的结构如何，这个公式都适用。即使数组 已经排序，直选排序算法仍然会进行 次比较。

这就是算法的时间复杂度为二次方的原因。尽管交换次数为 ，但比较次数使得直选排序算法的时间复杂度为二次方。

4. 总结

在这篇文章中，我们计算了直选排序算法的比较次数。如果输入数组有 个元素，算法将根据数组的结构进行 次比较。