标题：异或交换技巧的陷阱
出处：Felix021
时间：Thu, 19 Feb 2009 17:31:23 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1469

内容：
众所皆知，以下代码可以实现两个变量的交换：
int a, b;
a = a ^ b;
b = a ^ b;
a = a ^ b;

于是用这个写了一个随机化快速排序(防止特殊情况下的算法退化，代码很简单，如果认识快排，应该不难读懂)
void qsort(int a[], int s, int e){
    int i = s, j = e, t, p;
    if (s < e){
        p = rand() % (e - s + 1) + s;
        a[s] ^= a[p], a[p] ^= a[s], a[s] ^= a[p];
        t = a[s];
        while(i != j){
            while(i < j && a[j] > t) j--;
            if(i < j) a[i++] = a[j];
            while(i < j && a[i] < t) i++;
            if(i < j) a[j--] = a[i];
        }
        a[i] = t;
        qsort(a, s, i - 1);
        qsort(a, i + 1, e);
    }
}

看起来不错，可是运行结果不对，为什么呢？
因为这种方法在交换两个元素的值的时候有效，但是如果两个元素如果指向同一个地址，就会把它清零。
下面这段代码就正确了：
void qsort(int a[], int s, int e){
    int i = s, j = e, t, p;
    if (s < e){
        p = rand() % (e - s + 1) + s;
        t = a[s], a[s] = a[p], a[p] = t;
        t = a[s];
        while(i != j){
            while(i < j && a[j] > t) j--;
            if(i < j) a[i++] = a[j];
            while(i < j && a[i] < t) i++;
            if(i < j) a[j--] = a[i];
        }
        a[i] = t;
        qsort(a, s, i - 1);
        qsort(a, i + 1, e);
    }
}



Generated by Bo-blog 2.1.0