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,后自增。
我的理解哪里有问题?还是说这种写法的行为,取决于编译器的处理?
请大家帮忙看看。谢谢。
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
https://study.congcong.us/t/332252
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.