请教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++。