今天写快速排序的时候突发奇想,使用了一个无需中间变量的swap函数,但却出现了一些问题…
无需中间变量的swap函数如下:

1
2
3
4
5
void swap(int & a,int & b){
a = a + b;
b = a - b;
a = a - b;
}

快排函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void qSort(int a[],int s,int e){
if (s >= e) return;
int i = s;
int j = e;
int temp = a[s];
while(i != j){
while(i < j && a[j] > temp){
--j;
}
swap(a[i],a[j]);

while(i < j && a[i] < temp){
++i;
}
swap(a[i],a[j]);
}
qSort(a,s,i-1);
qSort(a,i+1,e);
}

原数组如下(全局):

1
int a[10] = {6,8,2,9,4,5,3,7,1,0};

当时我觉得这样写是没有问题的,但是!!!
鬼畜的一幕出现了:

1
0 0 0 0 0 5 0 0 8 0  //排序结果

思考与交流之后,出现这么多0原因是这样的:
快排代码中有两个index分别是i和j,虽然while循环的终止条件是i==j,但是这并不意味着在循环过程中i与j不会指向同一个数组元素(即i==j),当i==j时,swap函数的运行如下:

1
2
3
a[i] = a[i] + a[i];
a[i] = a[i] - a[i];
a[i] = a[i] - a[i];

由此可见,在swap第二行时,数组中该元素就已经被置0了,这也就解释了为什么未被置0元素的位置依然正确(因为这个函数只有下标相等才会出现错误,对排序无影响)。

总结:不要玩花的