遞歸奇怪的輸出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; 
}