G*******n
发帖数: 2041 | 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++。 |
l*****a
发帖数: 14598 | 2 写一个用a[right]做pivot的版本吧...
另外你的问题自己拿几个例子试试...
【在 G*******n 的大作中提到】
: 刚开始自己写，调了半天没搞出来，后来仔细对照书上的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)
: {
|
k***e
发帖数: 1931 | 3 qsort的partition我还是喜欢算法导论上的做法，拿第一个元素当pivot。反正取哪个
当pivot最优没有定论，面试的时候写成这样面试官也没法反驳。
一般来说partition就两个思路，一个是挖坑，左右两个指针，交替移动，不断挖坑填
坑，这个对两分比较形象，但是对于三分区间（小于，等于，大于）就有点难以理解了
，算法导论上面用的那个partition思路，对付两分三分都比较轻松。
【在 G*******n 的大作中提到】
: 刚开始自己写，调了半天没搞出来，后来仔细对照书上的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)
: {
|
m****y
发帖数: 43 | 4 leetcode哪里找quicksort的code啊？没有这题啊，course里也没有 |
G*******n
发帖数: 2041 | 5 不好意思，是cracking the coding interview里的code，见附件。我的问题是第13行
和第21行的等号
【在 m****y 的大作中提到】
: leetcode哪里找quicksort的code啊？没有这题啊，course里也没有
|
w***u
发帖数: 156 | |
t******i
发帖数: 35 | 7 感觉原因是因为如果不enforce left > right, partition 就有可能left=right
or left>right . 这样后面处理也要分这两张情况
[在 GreenBean (绿豆) 的大作中提到：]
：刚开始自己写，调了半天没搞出来，后来仔细对照书上的code，发现有两个细微区别
。但是不解为什么必须要这么做，请大侠指教。
：
：........... |
d******8
发帖数: 148 | 8
是的，问题出在这两行
【在 w***u 的大作中提到】
: 去掉23，24行试试
|
