Feb 19

异或交换技巧的陷阱 不指定

felix021 @ 2009-2-19 17:31 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(3890) | Via 本站原创 | |
众所皆知,以下代码可以实现两个变量的交换:
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);
    }
}




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]