为什么选择最佳情况不是 O(n)

Question

我看过很多话题，人们通常说选择排序的复杂度在最好的情况下仍然是 O(n^2)。但我无法被这些想法说服。例如，我想按升序顺序对数组进行排序。这是我在 Java 代码中的算法：

void selectionSort(int[] arr) {
    int min, temp;
    int length = arr.length;
    for (int i = 0; i <= length - 1; i++) {
        //System.out.println(i);
        min = i;
        for (int j = i+1; j < length ; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        if (min != i) {
            temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        } else {
            break;
        }
    }
}

我相信在最好的情况下这是 O(n)，即输入数组已经排序。我在此处添加到算法中的另一件事是检查是否 (min == i) 并中断循环。你怎么看？我错了吗？

Answer 1

选择排序中的两个循环都将完成运行 n 次。让我们以 [1,2,3,4,5]

为例

外层循环将运行 5 次，对于数组的每个值。然后内部循环将检查这是否是数组其余部分的最小值。

outer value = 1   -> Inner value 2,3,4,5
outer value = 2   -> Inner value 3,4,5
outer value = 3   -> Inner value 4,5
outer value = 4   -> Inner value 5
outer value = 5   -> Inner value none

此外，在您的代码中，此检查不正确

 else {
            break;
      }

说数组是[1,3,2]。在第一个外循环中，min ==i，它会中断甚至不会移动到下一个值。

Answer 2

SelectionSort 显然具有 O(N²) 时间复杂度，因为循环必须完全执行。比较的次数在所有情况下都是三角数T(N-1)，而交换的次数是线性的（在标准版本中）。

避免交换已经存在的元素可能不是一个好主意，因为它以非常低的概率有效并且在大多数情况下什么都不执行。（不算中断...破坏算法。）

为什么选择最佳情况不是 O(n)

Why selection best case is not O(n)

algorithm

sorting

time-complexity

selection-sort