交换函数调用的数目和选择排序相同对象时完成的交换数目吗？

Question

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

最佳情况：已完成1次交换。最坏的情况：完成n-1次交换。平均情况：完成（n-1）/ 2次交换。

所以，如果我说的是[[调用交换函数的次数与在3种不同情况下进行的交换次数相同，我会正确吗？

Answer 1

首先，我不确定为什么最小交换数将为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

但是，就您的[[actual问题而言，我敢打赌，他们是同一回事。除非您的swap函数具有在某些情况下可能无法交换的条件代码
（a）或每次交换不止一件事的代码，否则对swap函数的每次调用都与交换相同。
（（a）您
可以假设可以调用swap函数，而不管该项是否已经在正确的位置，并且它只是检测到该对象而不会交换，例如： void doSwap (Item *item1, Item * item2) {
    if (item1 != item2):
        Item tempItem = *item1;
        *item1 = *item2;
        *item2 = tempItem;
}

在那种情况下，对交换功能的调用可能与实际的交换不同。但是，老实说，由于函数调用虽然相对便宜，但很少花费零成本，因此检查可能更好地在上一层（根据伪代码）进行。