当下面的片段中的低等于高时,为什么下面的快速排序分区方法不能保证低/高左侧的元素小于枢轴,而低/高的右侧的元素大于枢轴 .
int middle = low + (high - low) / 2;
int pivot = a[middle];
while (low < high)
{
while (a[low] < pivot)
{
low++;
}
while (a[high] > pivot)
{
high--;
}
if (low <= high)
{
swap( a, low, high );
low++;
high--;
}
}
这不是“低”和“高”的定义是什么?一旦我们达到结束条件,在枢轴左侧和枢轴右侧表示元素?
考虑下面的数组
int[] a = {37, 89, 17, 51, 53, 75};
这里的低值等于索引1的高位,其中有元素89.但是,索引1是元素89的正确位置并不是正确的,索引1左边的元素都小于89,而右边的元素都是89 . 都超过89 .
为什么这个算法出错了?我希望曾经,低等于高,我们找到了该枢轴的正确位置,并且可以继续省略该元素,并递归地重复左边和右边的元素的算法 .