选择排序的最佳时间复杂度是什么？

Question

为什么选择排序的最佳时间复杂度是O(n^2)，而插入排序和冒泡排序的最佳时间复杂度却是O(n)?它们的平均时间相同。我不明白为什么最佳时间不同。希望能得到一些帮助。

- user3740951

---

可能是插入排序与选择排序的重复问题。 - Paul Hankin

Answer 1

选择排序需要搜索最小值并将其放在第一次迭代中的第一个位置。在第二次迭代中，您必须在数组的非排序部分中搜索最小值并将其放置在第二个位置，以此类推......

只有在迭代到非排序部分的末尾后，您才知道哪个元素是最小的。即使数组已经排序，您也必须迭代到末尾。然后，您可以确定找到了最小值，并将其放置在正确的位置（已排序部分的末尾）

因此，第一次迭代需要n步来查找最小值。 第二次迭代需要n-1步来在未排序部分中找到最小值 ...... 最后一次迭代需要1步来在未排序部分中查找最小值。

完成这些步骤后，您将拥有一个已排序的数组（即使它之前是已排序的）。选择排序不会通过线性时间算法检查数组是否已排序。选择排序重复搜索最小值。这就是选择排序的工作方式。

当您反复搜索最小值时，需要n+(n-1)+...+1步骤，因此您得到(n²+n)/2，这是O(n²)

- gartenkralle

---

正如你所提到的，如果数组已经排序，冒泡排序和插入排序将进行n次迭代。这比选择排序少了n^2步，因为我们需要对每个元素进行n次迭代。 - gartenkralle

在插入排序中，每次迭代中如果我们发现第一个要比较的元素比关键字小，那么我们就不需要再进行比较了。因此，对于已经排序好的数组，时间复杂度为O(n)。Ok got it. - user3740951

但是，当我们使用一个标志（对于最佳情况）将冒泡排序的复杂度从O（n ^ 2）优化为O（n）时，我们不能对选择排序进行相同的操作吗？ @gartenkralle - ANUPAM

@ANUPAM 两种算法的区别在于它们检查元素的方式。在冒泡排序中，您会在一次遍历中将每个元素与其相邻的元素进行比较，因此如果没有发生交换，则可以说该数组已排序。而在选择排序中，您仅将当前索引与未排序的一侧进行比较，因此无法从单次遍历中推断出未排序的一侧已排序，并被迫继续执行。 - Ryan McArthur

@RyanMcArthur请参考IDE中的代码： https://ide.geeksforgeeks.org/8b2e389e-4e30-4273-abb6-4c8d87e7c327 - ANUPAM