f*****w
发帖数: 2602 | 1 比如初始是 [5, 4, 3, 10, 9, 1, 2, 3, 5, 5, 5, 5]
partition之后的结果是 [5, 4, 3, 5, 5, 1, 2, 3, 5, 5, 9, 10]
我仔细看了我的实现没啥问题啊 就是照抄的；
书上说是两个循环往中间走 遇到相同的就交换，可是如果这样子的话难道不会肯定导
致某些5没法被挪
到中间去么？ 因为下一个外循环指针就离开当前5的位置继续往下了
这么个小破东西写对还真不容易啊... 绝望了 自己太菜了 | l******l
发帖数: 66 | 2 There is nothing wrong.
After partition, 9,10 is the second part, the rest is the first part, the
first part<=5, the second part >5.
Or maybe part 1=[5, 4, 3, 5, 5, 1, 2, 3,] part2 =[5, 5, 9, 10], part 1<=5,
part2>=5. | x******g
发帖数: 41 | 3 要是想分成xxx5555yyyy，x<5, y>5
看dutch flag那个算法 | r******g
发帖数: 13 | 4 3 way partition first puts the duplicated elements in two ends by scanning
once:
1. moving from let to find element not less < p
2. moving from right to find element not greater > p
3. exchange left and right elemnt
4. if (left elment == p) swap it with left end
5. if (right element == p) swap it with right end
=pivot, p, = pivot
my code got
5, 5, 5, 4, 3, 1, 2, 3, 5, 10, 5, 9
put the duplicated elements in the center by exchanging elements in two ends
and those in the center
3, 2, 1, 4, 3, 5, 5, 5, 5, 5, 10, 9
keep partitioning the subarrays, the array got sorted
1 2 3 3 4 5 5 5 5 5 9 10
it's not easy concept,not 100% sure my implementation is right, sign | f*****w
发帖数: 2602 | 5 dutch flag那个我在Algorithm C上看到写了下是对的
和这个Programming Pearl上的难道是一样的么？ | m**q
发帖数: 189 | 6 还有一种是单向的3-way partition，容易一些
这个双向的感觉更复杂
在 randneig (randneig) 的大作中提到: 】
scanning | p****e
发帖数: 37 | 7 void partition2(int v[], int b1, int e2, int& e1, int& b2)
{
if (e2 <= b1) return;
int pivot = v[e2];
int i = b1 - 1;
int j = e2;
int p = b1 -1;
int q = e2;
while (true)
{
while (v[++i] < pivot);
while (pivot < v[--j]) if (j <= b1) break;
if (i >= j)
break;
exch(v[i], v[j]);
if (v[i] == pivot) {exch(v[++p], v[i]);}
if (v[j] == pivot) {exch(v[--q], v[j]);}
}
exch(v[i], v[e2]);
j = i - 1;
i = i + 1;
for (int k = b1; k < p; ++k, --j) exch(v[k], v[j]);
for (int k = e2 - 1; k > q; --k, ++i) exch(v[k], v[i]);
e1 = j;
b2 = i;
}
Algorithm in C上面有，这段代码把v partition成 b1-e1, pivots, b2-e2三段 |
|
