快速排序:枢轴是第一个大于它的邻居的元素

Question

我正在学习快速排序，我发现了一个算法，其中pivot是第一个大于其邻居的元素，这里是伪代码

void quicksort(int i,int j)
{
pivotindex=findpivot(i,j);
if(pivotindex!=-1)
{
pivot=a[pivotindex];
k=partition(i,j,pivot); // l
quicksort(i,k-1);
quicksort(k,j);
}
}

int findpivot(int i, int j)
{
for i=0 to j
{
if(a[i]>a[i+1])
return(i);
else if(a[i]<a[i+1])
return(i+1);
else
continue;
}
return(-1);
}

int partition(int i, int j, int pivot)
{
int l, r;
l=i, r=j;
do
{
swap(a[l],a[r]);
while(a[l]<pivot)
l=l+1;
while(a[r]>=pivot)
r=r-1;
} while(l<r);
return(l);
}

这个伪代码可以正常工作吗?

我试着写c++代码，这是我的代码

#include <iostream>
using namespace std;
void swap(int *i,int *j){
int temp = *i;
*i = *j;
*j = temp;
}

int partition(int l, int r, int idx, int arr[]){

do{
int index = arr[idx];

swap(&arr[l],&arr[r]);

//cout<<arr[l]<<" "<<arr[r]<<" pivot : "<<index<<endl;

while(arr[l]<index){
l=l+1;
}
while(arr[r]>=index){
r=r-1;
}


}while(l<r);

return l;

}
int findpivot(int l,int r,int arr[]){

for(int i = l; i<=r; i++){
if(arr[i]>arr[i+1]){

return i;
} 
else if(arr[i+1]>arr[i]){

return i+1;
} 
else{
continue;
}

}
return(-1);

}

void Quicksort(int l, int r,int arr[]){

int idx = findpivot(l,r,arr);


if(idx!=-1){
int pivot = arr[idx];

int  k = partition(l,r,idx,arr);


Quicksort(l,k-1,arr);
Quicksort(k,r,arr);

}
}


int main()
{
int arr[10] = {19,23,11,43,24,68,98,47,99,89};
Quicksort(0,9,arr);

cout<<"final"<<endl;
for(int i =0;i<10;i++){
cout<<arr[i]<<" ";
}


return 0;
}

我的代码做得很好，直到这些步骤，然后它变成了一个无限循环，是我的代码有问题，还是伪代码错了?{43 89, 23岁,11日,24日,68年,98年,47岁,99年,19}

{19日,23日,11日,43岁,24岁,68年,98年,47岁,99年,89}

{43 19日,11日,23日,24日,68年,98年,47岁,99年,89}

{11日19}

谁能帮我这个忙。

Answer 1

除了@stark在关于伪代码在findpivot中迭代的初始值的注释中所说的，终止条件显然是不正确的。您的实现修复了初始值(可能是打字错误)，但在终止时重复了这个问题:for(int i = l; i<=r; i++).

但终止条件必须为i < r。如果i等于r，循环将访问元素a[r+1]，它在范围之外(可能在数组之外)。此外，该算法依赖于findpivot检测递归结束条件，即当范围内的所有元素相等时，而不是当范围内的所有元素与下一个元素相等时。这就是无尽循环。