删除Lomuto分区的最终交换

Question

为什么我们不能通过这个修改来避免lomuto分区中的最终交换语句？

int pivot=arr[h];
int i=l-1;
for(int j=l;j<=h;j++){
if(arr[j]<=pivot){
i++;
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
return i;

我的代码正确吗？

Answer 1

这是正确的！。排序有两种类型：稳定排序和不稳定排序。快速排序是一种不稳定的排序，因为元素的相对位置在快速排序中的分区过程中会发生变化。如果我们使用以下代码(<=(，那么如果我们使用您的代码，维护元素相对位置的效率会有所提高。

int pivot=arr[h];
int i=l-1;
for(int j=l;j<=h;j++){
if(arr[j]<=pivot){
i++;
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
return i;
}