C语言 在随机快速排序中查找麻烦(其中枢轴是随机数)

Question

int partition(int arr[], int low, int up)
{
int temp,i,j,pivot,k,swap;
i=low+1;
j=up;
k=(rand() % (up + 1 - low)) + low;
pivot=arr[k];
swap=arr[low];
arr[low]=arr[k];
arr[k]=swap;    
while(i<=j)
{
while((arr[i] < pivot) && (i < up))
{
i++;
}
while(arr[j] > pivot)
{
j++;
}
if(i < j)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
i++;
j--;
}
else
{
i++;
}
}
arr[low]=arr[j];
arr[j]=pivot;
return j;
}

我不知道我的代码出了什么问题，但它不起作用。当我给出 3、2、4 作为输入时，一个窗口对话框弹出"RandQck.exe已停止工作。问题导致程序停止正常工作"。 现在我在本节中做了一些修改，即

swap=arr[low];
arr[low]=arr[k];
arr[k]=swap;
pivot=arr[low];

给出输入 3、2、4，输出为 3,3,3。我知道这个问题很幼稚，但请帮助找出问题所在，如果可能的话，请纠正它。其余部分，即主部分，快速功能是正确的。问题仅出在分区功能上。

Answer 1

while(arr[j] > pivot)
{
j++;
}

这就是问题所在。 j++ 使数组脱离索引。让它成为j--.即

while(arr[j] > pivot)
{
j--;
}

Answer 2

这很有可能导致程序崩溃：

while(arr[j] > pivot){
j++;
}

变量j使用 up 初始化，并不断递增并超出数组的范围。

这是我使用的一个分区函数 (C++(，您可以使用随机初始透视来实现：

int partition(int* arr, int l, int u){
int flag=0;
int p = l; //I have initialized pivot with l, but it you can  choose a random value as well.
while(l<u){
if(flag == 0){
while(arr[u]>arr[p]) u--;
swap(&arr[u], &arr[p]);
flag=1;
p=u;
}
else if(flag == 1){
while(arr[l]<arr[p]) l++;
swap(&arr[l], &arr[p]);
flag=0;
p=l;
}
}
return p;
}