狂喜：无线路由器asus wl-520gu通过校园网锐捷802.11x认证！
Linux 守护进程的编程方法
Feb
19
众所皆知，以下代码可以实现两个变量的交换：
于是用这个写了一个随机化快速排序(防止特殊情况下的算法退化，代码很简单，如果认识快排，应该不难读懂)
看起来不错，可是运行结果不对，为什么呢？
因为这种方法在交换两个元素的值的时候有效，但是如果两个元素如果指向同一个地址，就会把它清零。
下面这段代码就正确了：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
int a, b;
a = a ^ b;
b = a ^ b;
a = 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);
}
}
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);
}
}
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 。
