选择排序时交换函数调用的次数和完成的交换次数是否相同？

Question

我知道对于 n 个元素，在选择排序中：

最佳情况： 1 次交换完成。 最坏情况：完成 n-1 次交换。 平均案例：完成 (n-1)/2 次交换。

所以，如果我说调用交换函数的次数与在 3 种不同情况下完成的交换次数相同，我是对的吗？

Answer 1

嗯，首先，我不确定为什么最小交换数会是一个。对于已经排序的数组，它应该为零。

任何半正经的算法都会检测到未排序部分中当前最小的项目已经在正确位置的事实，忘记交换并只是移动已排序和未排序部分之间的边界。

换句话说，类似于（伪代码）：

def selSort(items):
    # This position is the ever-moving border between
    # 'sorted on left' and 'unsorted from here to end'.

    for position in 0 thru items.length - 2 inclusive:
        # Scan all unsorted, finding the lowest (starting
        # default is the first unsorted).

        lowestUnsorted = position
        for checkPos = position + 1 thru items.length inclusive:
            # If lower than current lowest, replace.

            if items[checkPos] < items[lowestUnsoreted]:
                lowestUnsorted = checkPos

        # Swap if need be.

        if lowestUnsorted != position:
            temp = items[position]
            items[position] = items[lowestUnsorted]
            items[lowestUnsorted] = temp

但是，就您的实际问题而言，我敢打赌它们是同一回事。除非你的 swap 函数有条件代码在某些情况下可能不会交换 ^(a)，或者每次交换不止一个东西的代码，每次调用交换函数都是与交换相同。

^(a) 你可以证明交换函数可以被调用，而不管项目是否已经在正确的位置position 并且它只是检测到并且不交换，例如：

void doSwap (Item *item1, Item * item2) {
    if (item1 != item2):
        Item tempItem = *item1;
        *item1 = *item2;
        *item2 = tempItem;
}

在这种情况下，对交换函数的调用可能与实际交换不同。但是，老实说，这种检查最好在上面的层中完成（根据伪代码），因为函数调用虽然相对便宜，但很少是零成本的。

选择排序时交换函数调用的次数和完成的交换次数是否相同？

Is the number of swap function calls and the number of swaps done while selection sort the same thing?

c++

algorithm

sorting

data-structures

selection-sort