O******i
发帖数: 269 | 1 严蔚敏的老书介绍的是双指针向中间移动并交换，是Hoare的版本
CLRS介绍Lomuto版本的双指针一起向右边移动，前面的开路，后面的交换，类似荷兰旗
的方法
基于这两个方法的变种就更多了，选取pivot, 有选开头的，有选末尾的，有随机选的
，有选头，中，尾三个的median的...
编程珠玑专门开了一章讲它
可是，这些细节面试官基本不考的。
唯一有用的就是双指针大法，二爷认为该大法能解决一大票问题，包括直方图盛水,
Jump game, 有序数组去重... |
w****x
发帖数: 2483 | |
c*****a
发帖数: 808 | |
p*****2
发帖数: 21240 | 4 我看到题目正想说呢，又是two pointers. |
o***d
发帖数: 313 | 5 我怎么觉得两头往里容易的狠很多阿?
【在 w****x 的大作中提到】
: 没错，我个人认为双指针一起右移的更好实现
|
O******i
发帖数: 269 | 6 这个应该就是基于Hoare版本的，可能还是Lomuto版本的更容易写，不然不会被CLRS收
录到正文。Hoare的原始版本被CLRS放到课后习题去了。
【在 c*****a 的大作中提到】
: ![]() http://www.algolist.net/img/sorts/quick-sort.png
: 我就照着这个码.....前后指针跟pivot对比...找到适合然后交换
|
O******i
发帖数: 269 | 7 两头往里的代码更长些吧。
Lomuto的伪代码(t is pivot)很简短
m = a - 1
for i = [a, b]
if x[i] < t
swap(++m, i)
【在 o***d 的大作中提到】
: 我怎么觉得两头往里容易的狠很多阿?
|
o***d
发帖数: 313 | 8 效率高些么?否则两头的可读性高吧?容易维护,呵呵
【在 O******i 的大作中提到】
: 两头往里的代码更长些吧。
: Lomuto的伪代码(t is pivot)很简短
: m = a - 1
: for i = [a, b]
: if x[i] < t
: swap(++m, i)
|
O******i
发帖数: 269 | 9 二爷整理个full list吧，leetcode中能用广义双指针解的。
你的总结文中没有正式提到快排和荷兰旗。此外我觉得Jump Game I也是双指针
【在 p*****2 的大作中提到】
: 我看到题目正想说呢，又是two pointers.
|
O******i
发帖数: 269 | 10 Jump Game I的双指针法
bool canJump(int A[], int n)
{
int t = A[0];
if (t >= n - 1)
return true;
int s = 0;
while (s <= t)
{
if (s + A[s] > t)
{
t = s + A[s];
if (t >= n - 1)
return true;
}
s++;
}
return false;
} |
|
|
p*****2
发帖数: 21240 | 11
我也在总结的过程中，准备一步一步的来。
快排没有提到是因为Leetcode中没有，面试也不常见。哈兰旗就是color sort吧。Jump
Game我一会儿看一下，感觉是。我的整理现在也还不是很全面。
【在 O******i 的大作中提到】
: 二爷整理个full list吧，leetcode中能用广义双指针解的。
: 你的总结文中没有正式提到快排和荷兰旗。此外我觉得Jump Game I也是双指针
|
O******i
发帖数: 269 | 12 荷兰旗和快排有很大联系，就是leetcode的 color sort。
我记得张弛的F面试就被问到荷兰旗，他的标准无误解法还被老印质疑有bug。
Jump
【在 p*****2 的大作中提到】
:
: 我也在总结的过程中，准备一步一步的来。
: 快排没有提到是因为Leetcode中没有，面试也不常见。哈兰旗就是color sort吧。Jump
: Game我一会儿看一下，感觉是。我的整理现在也还不是很全面。
|
w****x
发帖数: 2483 | 13
Jump
当年做荷兰旗的时候只会两边夹的那种快排，所以code麻烦死，后来知道了荷兰旗的两
指针一起往右移动的解法，当时感觉就是很难想到，后来才看到两指针一起往右移的快
排方法，当时一看就想，我靠，这不是荷兰旗吗，其实顺序是反过来的...
【在 p*****2 的大作中提到】
:
: 我也在总结的过程中，准备一步一步的来。
: 快排没有提到是因为Leetcode中没有，面试也不常见。哈兰旗就是color sort吧。Jump
: Game我一会儿看一下，感觉是。我的整理现在也还不是很全面。
|
O******i
发帖数: 269 | 14 再加几个
两个pointers从两头往中间走，可以用于reverse string和判断是否palindrome
两个pointers从头往后走，有一类是读写头法，常常用于in place的去重或者删除元素
。PIE书中去除string中的元音字母aeiou介绍了这种方法，此外可以用于有序数组去重
，还有把字符串中空格替换为%20 |
O******i
发帖数: 269 | 15 清华严蔚敏的书只介绍两边夹的方法，所以很多人都先入为主了，那本书至少也应该提
一下别的方法，虽然两边夹的方法是快排鼻祖Hoare的最早方法。
另外荷兰旗对相同元素的处理更好，pivot从单个数扩展为中间一段相同的数。
【在 w****x 的大作中提到】
:
: Jump
: 当年做荷兰旗的时候只会两边夹的那种快排，所以code麻烦死，后来知道了荷兰旗的两
: 指针一起往右移动的解法，当时感觉就是很难想到，后来才看到两指针一起往右移的快
: 排方法，当时一看就想，我靠，这不是荷兰旗吗，其实顺序是反过来的...
|
p*****2
发帖数: 21240 | 16
我color sort是自己做的。只会两边夹的快排。你们说的两个指针一起走的我没看过。
不过我感觉我的代码也挺简洁的。
【在 w****x 的大作中提到】
:
: Jump
: 当年做荷兰旗的时候只会两边夹的那种快排，所以code麻烦死，后来知道了荷兰旗的两
: 指针一起往右移动的解法，当时感觉就是很难想到，后来才看到两指针一起往右移的快
: 排方法，当时一看就想，我靠，这不是荷兰旗吗，其实顺序是反过来的...
|
w****x
发帖数: 2483 | 17
跪求面向对象语言版本
【在 p*****2 的大作中提到】
:
: 我color sort是自己做的。只会两边夹的快排。你们说的两个指针一起走的我没看过。
: 不过我感觉我的代码也挺简洁的。
|
O******i
发帖数: 269 | 18 zhangchi贴过代码的
http://www.mitbbs.com/article/JobHunting/32089461_3.html
其实是三个指针。不过前面两个指针就是一起走，第三个指针向中间走。
前两个指针的走法，就类似CLRS快排那节介绍的Lomuto法给数组partition
【在 p*****2 的大作中提到】
:
: 我color sort是自己做的。只会两边夹的快排。你们说的两个指针一起走的我没看过。
: 不过我感觉我的代码也挺简洁的。
|
p*****2
发帖数: 21240 | 19
太巧了，跟我的解法几乎一模一样。
【在 O******i 的大作中提到】
: zhangchi贴过代码的
: http://www.mitbbs.com/article/JobHunting/32089461_3.html
: 其实是三个指针。不过前面两个指针就是一起走，第三个指针向中间走。
: 前两个指针的走法，就类似CLRS快排那节介绍的Lomuto法给数组partition
|
