algorithm - 选择排序运行时困惑

Question

根据 http://algs4.cs.princeton.edu/21elementary/“选择排序使用 ~N²/2 次比较和 N 次交换来对长度为 N 的数组进行排序。”
例如，我在数组中有两个项目。
String[] a = {"h","t"};
我可以假设选择排序使用 2²/2 = 2 次比较和 2 次交换来对长度为 2 的数组进行排序吗？
但是当我运行这个时: http://algs4.cs.princeton.edu/21elementary/Selection.java.html只比较过一次。当然这是常识，因为唯一要比较的项目是 h 和 t。但我仍然对声明感到困惑。他们的实验有问题吗？我是新手。

Answer 1

选择排序使用大约 N^2/2 次比较和 N 次交换。

对于精确分析，选择排序使用

N-1 + N-2 + N-3 + .....1 次比较，对长度为 N 的数组进行排序。

因此，比较总数 = (N-1)*(N)/2 = N^2/2 - N/2 大约等于 N^2/2 。这是他们写的。

在您的示例中，当 N 为 2 时，比较 = 1*2/2 = 1。且交换次数=1。(N-1)