我已经实现了以下快速排序算法来对点(3D 空间)进行排序。 每对夫妇定义一条线:目的是将距离小于或等于 powR 的所有线放在包含所有夫妇的数组附近。 包含坐标的数组是一维的,每6个元素定义一对,每3个元素定义一个点。
当我运行包含 3099642 个元素的数组的算法时,在处理完 2799222 个元素后停止尝试进入下一次迭代。如果我从元素 2799228 开始算法,它会在 3066300 处停止。 我无法弄清楚问题出在哪里,有建议吗?
void QuickSort(float *array, int from, int to, float powR){
float pivot[6];
float temp[6];
float x1;
float y1;
float z1;
float x2;
float y2;
float z2;
float d12;
int i;
int j;
if(from >= to)
return;
pivot[0] = array[from+0];
pivot[1] = array[from+1];
pivot[2] = array[from+2];
pivot[3] = array[from+3];
pivot[4] = array[from+4];
pivot[5] = array[from+5];
i = from;
for(j = from+6; j <= to; j += 6){
x1 = pivot[0] - array[j+0];
y1 = pivot[1] - array[j+1];
z1 = pivot[2] - array[j+2];
x2 = pivot[3] - array[j+3];
y2 = pivot[4] - array[j+4];
z2 = pivot[5] - array[j+5];
d12 = (x1*x1 + y1*y1 + z1*z1) + (x2*x2 + y2*y2 + z2*z2);
/*the sorting condition i am using is the regular euclidean norm*/
if (d12 <= powR){
i += 6;
temp[0] = array[i+0];
temp[1] = array[i+1];
temp[2] = array[i+2];
temp[3] = array[i+3];
temp[4] = array[i+4];
temp[5] = array[i+5];
array[i+0] = array[j+0];
array[i+1] = array[j+1];
array[i+2] = array[j+2];
array[i+3] = array[j+3];
array[i+4] = array[j+4];
array[i+5] = array[j+5];
array[j+0] = temp[0];
array[j+1] = temp[1];
array[j+2] = temp[2];
array[j+3] = temp[3];
array[j+4] = temp[4];
array[j+5] = temp[5];
}
}
QuickSort(array, i+6, to, powR);
}
函数是这样调用的: float LORs = (float) calloc((unsigned)tot, sizeof(float));
LORs 是从文件中读取数据填充的,并且工作正常。
QuickSort(LORs, 0, 6000, powR);
free(LORs);
最佳答案
for(j = from+6; j <= to; j += 6) {
array[i+0] = array[j+0];
array[i+1] = array[j+1];
array[i+2] = array[j+2];
array[i+3] = array[j+3];
array[i+4] = array[j+4];
array[i+5] = array[j+5];
}
当您接近终点时,您的j + constant_number
越界
。这就是它最后崩溃的原因。请注意,constant_number 是非负数。
当 j
接近数组末尾时(您可以通过递增步骤找到多接近,即 +6),它肯定会越界。
取最简单的情况,j
可以得到的最大值。那就是你的数组的大小。
所以,我们称它为 N。
然后,当j等于N时,就进入循环。
然后,你要访问array[j + 0]
,其实就是array[N + 0]
,也就是array[N]
.
我很确定,您知道 C 中的索引(您将来应该将其包含在您的问题标签中是必需的)是从 0 到 N - 1。依此类推。
编辑:正如评论所暗示的,这不是(快速)排序!
我实现了快速排序 here ,您想了解一下吗?我建议您从解释开始,而不是从代码开始!
关于c - 快速排序算法在一些迭代后就地崩溃,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23393765/