请教leetcode里quicksort的code# JobHunting - 待字闺中
G*n
1 楼
刚开始自己写，调了半天没搞出来，后来仔细对照书上的code，发现有两个细微区别。
但是不解为什么必须要这么做，请大侠指教。
两个细微差别是在partition里：
int Partition3(int *a, int left, int right)
{
int pivot = a[(left + right) / 2];
while (left < right) //leetcode: while (left <= right)
{
while (a[left] < pivot)
{
left++;
}
while (a[right] > pivot)
{
right--;
}
if (left < right) //leetcode: if (left <= right)
{
int temp = a[left];
a[left] = a[right];
a[right] = temp;
left++;
right--;
}
}
return left;
}
我没加等号是因为：
1. while (left < right)，没加等号，是因为如果left == right，那就只有一个数，
没必要做了
2. if (left < right)， 没加等号，是因为如果想等，就没必要swap了
可是这两处不加等号根本就不work。我看了下，加等号跟不加等号的最大区别是会不会
做left++ （partition的返回值不一样）；可是为什么在left和right相等的时候必须
要返回left++。
但是不解为什么必须要这么做，请大侠指教。
两个细微差别是在partition里：
int Partition3(int *a, int left, int right)
{
int pivot = a[(left + right) / 2];
while (left < right) //leetcode: while (left <= right)
{
while (a[left] < pivot)
{
left++;
}
while (a[right] > pivot)
{
right--;
}
if (left < right) //leetcode: if (left <= right)
{
int temp = a[left];
a[left] = a[right];
a[right] = temp;
left++;
right--;
}
}
return left;
}
我没加等号是因为：
1. while (left < right)，没加等号，是因为如果left == right，那就只有一个数，
没必要做了
2. if (left < right)， 没加等号，是因为如果想等，就没必要swap了
可是这两处不加等号根本就不work。我看了下，加等号跟不加等号的最大区别是会不会
做left++ （partition的返回值不一样）；可是为什么在left和right相等的时候必须
要返回left++。
