为什么说选择排序具有 O(n) 交换？
Why is Selection Sort said to have O(n) swaps?
我正在阅读有关选择排序的用例，this source 说：
(selection sort is used when...) cost of writing to a memory matters like in flash memory (number of writes/swaps is O(n) as compared to O(n2) of bubble sort)
我们甚至可以在这个例子中看到 O(n^2) 次交换：
[1, 2, 3, 4, 5]。它将进行 4 次交换，然后是 3 次，然后是 2 次和 1 次。即 O(n^2)，而不是 O(n)互换。为什么他们说相反？
选择排序的时间复杂度为O(n2)，但只有O(n)次交换。
在每次迭代 i 中，您遍历所有剩余项目（索引 i 及以后），找到正确的值来填充该索引，并在那里交换它。因此，您总共执行 O(n2) 比较 ，但仅执行 O(n) 次交换。
我正在阅读有关选择排序的用例，this source 说：
(selection sort is used when...) cost of writing to a memory matters like in flash memory (number of writes/swaps is O(n) as compared to O(n2) of bubble sort)
我们甚至可以在这个例子中看到 O(n^2) 次交换：
[1, 2, 3, 4, 5]。它将进行 4 次交换，然后是 3 次，然后是 2 次和 1 次。即 O(n^2)，而不是 O(n)互换。为什么他们说相反？
选择排序的时间复杂度为O(n2)，但只有O(n)次交换。
在每次迭代 i 中，您遍历所有剩余项目（索引 i 及以后），找到正确的值来填充该索引，并在那里交换它。因此，您总共执行 O(n2) 比较 ，但仅执行 O(n) 次交换。