java - 使用java为插入排序调试xor-swap

Question

我使用 xor-swap 的插入排序不工作，但没有 xor-swap 它工作正常。如何修复我的异或交换插入排序算法？

没有异或交换的插入排序 -

//sorts the given array in " increasing order "
   private static void insertionSort(char[] array) {
     // save the length of array 
      final  int  LENGTH = array.length ;

    //loop through selecting second character as  first element is already sorted
        for(int i = 1 ; i < LENGTH ; ++i )
             {
            char current  =  array[i];
            //place the array[i] in "order" with elements placed towards left of itself
                  for( int j = i - 1 ; (j >=0 && array[j+1] < array[j]) ; --j )
                  {


                      array[j+1] = array[j] ;
                      array[j] = current ;
                  }
              }



    }

用异或交换--

//sorts the given array in " increasing order "
    private static void insertionSort(char[] array) {
         // save the length of array 
          final  int  LENGTH = array.length ;

          //loop through selecting second character as  first element is already sorted
          for(int i = 1 ; i < LENGTH ; ++i )
    {
              //char current  =  array[i];
     //place the array[i] in "order" with elements placed towards left of itself
              for( int j = i - 1 ; (j >=0 && array[j+1] < array[j]) ; --j )
              {

                  array[j+1] ^= array[j] ^=  array[j+1] ^= array[j] ;
                  //array[j] = current ;
              }
          }




    }

谢谢

Answer 1

执行顺序与 ^= 运算符右关联，因此您编写的代码等同于:

a ^= (b ^= (a ^= b));

^= 运算符只是 a = a ^ b 的简写，所以如果你完全展开它，你会得到:

a = a ^ (b = b ^ (a = a ^ b));

现在请记住，a 的值将在表达式求值开始时获取，而不是在执行时获取。假设 a 和 b 取值 5 和 10。您正在有效地计算:

a = 5 ^ (b = 10 ^ (a = 5 ^ 10));

您实际上需要第一个 5 为 15 才能使交换工作。

因此，正如 Alan Stokes 所指出的，您需要将表达式分成三个(或两个)语句，以便告诉编译器每个语句的结果应该用于下一阶段的计算。

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