K*****k
发帖数: 430 | 1 典型的Hoare双向扫描Partition法一般都会在左右设置sentinel, 或者对左右边界检测
下标越界，这个非典型的代码却不用。
int Partition(int arr[], int left, int right)
{
int pivot = arr[left + (right - left) / 2];
while (left <= right)
{
while (arr[left] < pivot]
left++;
while (arr[right] > pivot]
right--;
if (left <= right)
{
swap(arr, left, right);
left++;
right--;
}
}
return left;
} | e***l
发帖数: 710 | 2 if (left <= right)
应该是if (arr[left] >= arr[right])
正确性是显然的，左边不大于pivot,右边不小于pivot | K*****k
发帖数: 430 | 3 代码来自CareerCup那本书
CLRS和编程珠玑都喜欢讲解Lumoto版本的Partition
编程珠玑提到的Hoare版本Partition，每次都需要检测右边界 (i <= u)，
看去效率稍低
...
t = x[L]; i = L; j = U + 1;
loop
do i++; while i <= u && x[i] < t
do j--; while x[j] > t
if (i > j)
break;
swap(i, j)
end loop
swap(L, j)
...
【在 e***l 的大作中提到】
: if (left <= right)
: 应该是if (arr[left] >= arr[right])
: 正确性是显然的，左边不大于pivot,右边不小于pivot
|
|
