使用 xor 或 temp 的冒泡排序

Question

在使用冒泡排序算法对数组进行排序的情况下，在嵌套循环内创建临时变量或使用 xor 运算符更有效：

#include <iostream>

int main()
{  
    int array[5] = {7, 2, 5, 3, 4};

    /*1: using temporary variable

    for(int i(0); i < 5; i++)
    {
        for(int j(i + 1); j < 5; j++)
        {
            if(array[i] > array[j])
            {
                int tmp  = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
    }
    */

    //2: using xor ^ swapper
    for(int i = 0; i < 5; i++)
    {
        for(int j(i + 1); j < 5; j++)
        {
            if(array[i] > array[j])
            {
                array[i] ^= array[j];
                array[j] ^= array[i];
                array[i] ^= array[j];
            }
        }
    }


    for( i = 0; i < 5; i++)
        std::cout << array[i] << ", ";

    std::cout << std::endl;
    return 0;
}

我只想知道哪个更快更强大，因为这两种方法都可以正常工作。

Answer 1

正如其他人已经指出的那样，唯一确定的方法就是测量它。

"how to measure it?" 本来是一个完全不同的问题的主题，如果这样的问题是关于 Whosebug 的主题的话。但事实并非如此。

Google 是你的朋友。 Google它。查找 "benchmark" 或 "profile" 等关键字以及 "C++" 以及您正在使用的 IDE 的名称。

除此之外，我可以通过检查说明给您一些很好的指示，告诉您哪个更快。

指令序列

  a ^= b;
  b ^= a;
  a ^= b;

转换为以下未优化的指令：

  load  register from a            ;memory reference
  xor   register with b            ;memory reference
  store register to a              ;memory reference
  load  register from b            ;memory reference
  xor   register with a            ;memory reference
  store register to b              ;memory reference
  load  register from a            ;memory reference
  xor   register with b            ;memory reference
  store register to a              ;memory reference

可能如下优化：

  load  register1 from a           ;memory reference
  load  register2 from b           ;memory reference
  xor register1 with register2
  xor register2 with register1
  xor register1 with register2
  store register1 to a             ;memory reference
  store register2 to b             ;memory reference

指令序列

  int tmp  = a;
  a = b;
  b = tmp;

转换为以下未优化的指令：

  load  register from a            ;memory reference
  store register to tmp            ;memory reference
  load  register from b            ;memory reference
  store register to a              ;memory reference
  load  register from tmp          ;memory reference
  store register to b              ;memory reference

可能如下优化：

  load register1 from a            ;memory reference
  load register2 from b            ;memory reference
  store register1 to b             ;memory reference
  store register2 to a             ;memory reference

正如你所看到的，两个优化的片段都只涉及四个内存引用，所以这两种方法大致相等，但是 XOR 方法涉及 3 个额外的指令，所以它不可能表现得更好。

不相信我？那么，不要相信我的话！我什至无法确定您的编译器可能能够执行哪些类型的额外优化。因此，除了运行基准测试或分析代码之外，还请尝试查看编译器为上述代码片段生成的程序集。（当然，启用了所有优化。）

使用 xor 或 temp 的冒泡排序

bubble sort with xor or temp

c++

bubble-sort