递归奇怪的输出QuickSort

Question

我想在C中实现递归快速排序，通过使用按位异或操作进行所有交换。这里是我有这么远：

//bitwise recursive quicksort 
void quicksort(int *int_array,int p, int r){ 
    if(p<r){ 
      int q = part(int_array, p, r); 
      quicksort(int_array,p, q-1); 
      quicksort(int_array, q+1, r); 
    } 
} 
//Partition 
int part(int *int_array, int p, int r){ 
    int pivot = int_array[r]; 
    int i = p-1; 
    int j; 
    for(j = p; j<=r-1; j++){ 
      if(int_array[j] <= pivot){ 
        i++; 
        int_array[i] = int_array[i]^int_array[j]; 
        int_array[j] = int_array[i]^int_array[j]; 
        int_array[i] = int_array[i]^int_array[j]; 

      } 
    } 
    int_array[i+1] = int_array[i+1]^int_array[r]; 
    int_array[r] = int_array[i+1]^int_array[r]; 
    int_array[i+1] = int_array[i+1]^int_array[r]; 
    return i+1; 
} 

当我运行的20个整数，19个其中20阵列上的代码获得变为0的任何想法，为什么？我无法看到XOR交换的任何错误。任何帮助表示感谢，谢谢！

Answer 1

XOR交换算法在与自己交换项目时不起作用，因为任何与其自身异或的数字都将为0，算法依赖于存在两个位置。所以在第一行之后，你刚刚抹去了价值。

XOR swap algorithm：

然而，该算法，如果x和y使用相同的存储位置，由于存储在该位置的值将被第一XOR指令置零，然后保持为零失败;它不会“自行调换”。请注意，这与x和y具有相同的值不一样。麻烦只发生在x和y使用相同的存储位置时，在这种情况下，它们的值必须已经相等。

你可以把周围的掉期测试，以确保你没有尝试过换一个元素与自身：

int part(int *int_array, int p, int r){ 
    int pivot = int_array[r]; 
    int i = p-1; 
    int j; 
    for(j = p; j<=r-1; j++){ 
      if(int_array[j] <= pivot){ 
        i++; 
        if(i != j) // avoid XORing item with itself 
        { 
         int_array[i] = int_array[i]^int_array[j]; 
         int_array[j] = int_array[i]^int_array[j]; 
         int_array[i] = int_array[i]^int_array[j]; 
        } 
      } 
    } 
    if(i+1 != r) // avoid XORing item with itself 
    { 
     int_array[i+1] = int_array[i+1]^int_array[r]; 
     int_array[r] = int_array[i+1]^int_array[r]; 
     int_array[i+1] = int_array[i+1]^int_array[r]; 
    } 
    return i+1; 
}