y***n
发帖数: 1594 | 1 上次看了一个人贴了Google 问了3-way Partition, 自己试了一下，写的很难看， 后
来看了一下
Princeton 的书，就这么几行，面试时候写出来还真不不容易。。
也许是我转行的水平太差。。还得修炼。。
http://algs4.cs.princeton.edu/23quicksort/Quick3way.java.html
private static void partition(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, gt = hi;
Comparable v = a[lo];
int i = lo;
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) exch(a, lt++, i++);
else if (cmp > 0) exch(a, i, gt--);
else i++;
}
} | b***y
发帖数: 177 | 2 其实就是leetcode的sortcolor
【在 y***n 的大作中提到】
: 上次看了一个人贴了Google 问了3-way Partition, 自己试了一下，写的很难看， 后
: 来看了一下
: Princeton 的书，就这么几行，面试时候写出来还真不不容易。。
: 也许是我转行的水平太差。。还得修炼。。
: http://algs4.cs.princeton.edu/23quicksort/Quick3way.java.html
: private static void partition(Comparable[] a, int lo, int hi) {
: if (hi <= lo) return;
: int lt = lo, gt = hi;
: Comparable v = a[lo];
: int i = lo;
| l*********8
发帖数: 4642 | 3 c/c++ 可以写成这样。
void partition(int * low, int * high, int pivot) {
for (int *p = low; p < high; ) {
if (*p == pivot)
++p;
else if (*p < pivot)
swap(*low++, *p++);
else
swap(*p, *--high);
}
}
【在 y***n 的大作中提到】
: 上次看了一个人贴了Google 问了3-way Partition, 自己试了一下，写的很难看， 后
: 来看了一下
: Princeton 的书，就这么几行，面试时候写出来还真不不容易。。
: 也许是我转行的水平太差。。还得修炼。。
: http://algs4.cs.princeton.edu/23quicksort/Quick3way.java.html
: private static void partition(Comparable[] a, int lo, int hi) {
: if (hi <= lo) return;
: int lt = lo, gt = hi;
: Comparable v = a[lo];
: int i = lo;
| y**********u
发帖数: 6366 | 4 这个swap有问题阿
后
【在 l*********8 的大作中提到】
: c/c++ 可以写成这样。
: void partition(int * low, int * high, int pivot) {
: for (int *p = low; p < high; ) {
: if (*p == pivot)
: ++p;
: else if (*p < pivot)
: swap(*low++, *p++);
: else
: swap(*p, *--high);
: }
| b******t
发帖数: 965 | 5 leetcode上面好多题都很难啊 能想出来要花很久
【在 y***n 的大作中提到】
: 上次看了一个人贴了Google 问了3-way Partition, 自己试了一下，写的很难看， 后
: 来看了一下
: Princeton 的书，就这么几行，面试时候写出来还真不不容易。。
: 也许是我转行的水平太差。。还得修炼。。
: http://algs4.cs.princeton.edu/23quicksort/Quick3way.java.html
: private static void partition(Comparable[] a, int lo, int hi) {
: if (hi <= lo) return;
: int lt = lo, gt = hi;
: Comparable v = a[lo];
: int i = lo;
| y**********u
发帖数: 6366 | 6 大牛你的算法这么厉害。。。
后
【在 b******t 的大作中提到】
: leetcode上面好多题都很难啊 能想出来要花很久
| l*********8
发帖数: 4642 | 7 high 是指向数组最后一个元素的后面一个。
比如：
int a[5] = {3,2, 7, 2, 1};
int pivot = 2;
partition(a, a+5, pivot);
【在 y**********u 的大作中提到】
: 这个swap有问题阿
:
: 后
| y**********u
发帖数: 6366 | 8 算法没有问题阿
主要是swap，pass by value可能不那么好
【在 l*********8 的大作中提到】
: high 是指向数组最后一个元素的后面一个。
: 比如：
: int a[5] = {3,2, 7, 2, 1};
: int pivot = 2;
: partition(a, a+5, pivot);
| l*********8
发帖数: 4642 | 9 std::swap是pass by reference的啊
【在 y**********u 的大作中提到】
: 算法没有问题阿
: 主要是swap，pass by value可能不那么好
|
|
