C语言快速排序中异或实现的swap函数运行异常是什么原因？

异或swap函数的问题根因 #

异或交换逻辑有一个致命的前提限制：参与交换的两个指针不能指向同一块内存地址。
当x和y指向同一个地址时：

1. 第一步*x = *x ^ *y等价于*x = *x ^ *x，直接将该地址的值置为0
2. 后续两次异或操作的结果也永远是0，最终该位置的原值被彻底清空为0

代码触发场景 #

在partition函数的末尾执行swap(&a[low], &a[j])时，极容易出现low == j的情况（比如当前分区的基准值已经在正确位置，不需要交换），此时两个入参指针指向同一个数组元素，直接触发上述bug，将基准值清0，导致最终排序结果全是异常的0值。

修复方案 #

1. 更推荐直接使用临时变量版本的swap：没有额外前提限制，可读性更高，现代编译器对临时变量交换的优化效果远好于异或写法，实际执行性能更高
2. 若一定要保留异或swap写法，需要先增加指针相等的判断逻辑：

void swap(int *x, int *y)
{
    // 指针相同时直接跳过，避免同地址交换bug
    if (x == y) return;
    *x = *x ^ *y;
    *y = *y ^ *x;
    *x = *x ^ *y;
}

内容的提问来源于stack exchange，提问作者Milan