sorting - 删除 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;

我的代码正确吗？

标签： sortingdata-structuresquicksortpartitioning

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;
}