这是一个创建于 2872 天前的主题，其中的信息可能已经有所发展或是发生改变。
EXAMPLE 3-1 . Quicksort function
void quicksort(int l, int u)
{ int i, m;
if (l >= u) return;
swap(l, randint(l, u));
m = l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
swap(l, m);
quicksort(l, m-1);
quicksort(m+1, u);
}
写这章的人，就是发明这个算法的人。我看了下其当时写的论文，也的确是这样写的。
但是，我有点理解不了 swap(++m,l)这个函数调用。++m 应该是先增，然后再推入栈，那么其每次 while 循环在 swap 相同的元素。我测试了下 gcc 5.4，的确在 swap 相同元素。
而且英文维基百科，写的算法，也是先swap，后自增。
我的理解哪里有问题？还是说这种写法的行为，取决于编译器的处理？
请大家帮忙看看。谢谢。
void quicksort(int l, int u)
{ int i, m;
if (l >= u) return;
swap(l, randint(l, u));
m = l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
swap(l, m);
quicksort(l, m-1);
quicksort(m+1, u);
}
写这章的人，就是发明这个算法的人。我看了下其当时写的论文，也的确是这样写的。
但是，我有点理解不了 swap(++m,l)这个函数调用。++m 应该是先增，然后再推入栈，那么其每次 while 循环在 swap 相同的元素。我测试了下 gcc 5.4，的确在 swap 相同元素。
而且英文维基百科，写的算法，也是先swap，后自增。
我的理解哪里有问题？还是说这种写法的行为，取决于编译器的处理？
请大家帮忙看看。谢谢。
 |
1
adaofu123 OP 额。明白了，的确是在 swap 相同元素。
但是 while 循环的目的，不是改变元素顺序，而是将 m 递增并把小于 l 的元素赋值给 m 递增后对应的元素， i 对应的元素不变化。 while 循环之后，哨兵 m 就是 l 对应元素排序后应该处的位置。 |
 |
2
jedihy 2017-02-17 02:50:03 +08:00
能把这个原算法论文贴一下？
|
Select Language