金家确实是吃货,,,# Joke - 肚皮舞运动
K*k
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;
}
下标越界,这个非典型的代码却不用。
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;
}