在 C 语言中，为什么交换 x 和 y 比交换 y 和 x 更快？

Question

一道题minimum-swaps-2，arr是未排序数组，arr_count是数组元素个数，我们需要return最小交换次数来排序数组，

我试过了：

int minimumSwaps(int arr_count, int* arr) {
    int swap = 0;
    for(int i  = 0; i < arr_count;){
        if(arr[i] != (i + 1)){
            int temp = arr[i];
            arr[i] = arr[arr[i] - 1];
            arr[arr[i] - 1] = temp;
            swap++;
        } else {
            i++;
        }
    }
    return swap;
}

但是没用。它显示超时错误。即运行花费了更多时间！然后我尝试了下面的代码，成功了！

        int temp = arr[arr[i] - 1];
        arr[arr[i] - 1] = arr[i];
        arr[i] = temp;
        swap++;

两者之间的唯一区别是将 x 与 y 或 y 与 x 交换。这有什么区别？

Answer 1

在 arr[i] = arr[arr[i] - 1]; 值 arr[i] 更改后 arr[arr[i] - 1] 不再指向同一存储，arr[arr[i] - 1] = temp; 写入了错误的存储。

所以你实际上并没有交换两个值。如果将其表示为指针算术，它可能会很明显。

        int temp = *(arr + i);
        *(arr + i) = *(arr + temp - 1);
        *(arr + *(arr + i) - 1) = temp;

最后一行等于 *(arr + *(arr + temp - 1) - 1)，其值在第 2 行执行之前出现，根据任务定义这是错误的。

事实上它给出了明显的解决方案：

        int temp = *(arr + i);
        *(arr + i) = *(arr + temp - 1);
        *(arr + temp - 1) = temp;

或

        int temp = arr[i];
        arr[i] = arr[temp - 1];
        arr[temp - 1] = temp;

产生从 minimumSwaps.

返回的结果 5

基本上你超时了，因为第一个变体无法找到解决方案。

在 C 语言中，为什么交换 x 和 y 比交换 y 和 x 更快？

In C, why swapping x with y is faster then swapping y with x?

c

arrays

sorting

swap