要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？ 第1页

这玩意儿还谈不上算法。不过作为一个最简题目，拿来训练算法分析还是有点用的。

首先分析它的复杂度。

这道题本质上要求知道12相对于其它每个数是更大或者更小；那么要知道这个信息，我们就必须让12和每个数比一次大小——少了肯定排不对位置，对吧；反过来说也对：只要和每个数比较一次，我们就一定知道12应该在哪个位置。

于是，我们知道，这道题目的复杂度不可能低于O(N)；但与之同时，写出高于O(N)的算法也是不可饶恕的。

最容易想到的做法就是拿出每个数和12比较；大于12就放到一个数组里，小于12则放到另一个数组里；搞完两个数组一拼，结束。

这个做法也的确是O(N)的时间效率。甚至可能是时间效率最高的算法。因为每个数都和12比较了恰巧一次。

但这种做法需要额外的空间。考虑所有数字都大于/小于12的情况，我们需要2N的空间。换句话说空间复杂度是O(N)。

但很容易看出，空间复杂度O(N)并不是必需的。因此这里有很大的优化空间。

比如，我们可以把12看作数组里的“浮标”；从它开始，分别和自己左右两边的数字比较，大于12就放右边、小于12放左边，这样无需额外的空间消耗，排序就完成了。

但现在的问题是，12左右两侧的元素数目不太可能恰好和大于12/小于12的元素数目相等。因为12是必然要移动位置的。

那么，怎么才能正确移动12的位置呢？

一个简单的做法是：先用12和每个数字比较，记录下12在其中的次序idx；那么12最终应该在的位置就是数组第idx个元素处。

计算出来idx后，把12置于idx处，然后逐一检查其左侧的每个元素，发现它大于12就到右侧找一个低于12的元素（记住这个位置idx2，下次从这里继续查找即可），交换两者的位置。

这种做法相当于要做2N次比较，第一次找出12应该在的位置、第二次调整两边的元素位置；空间复杂度O(1)——除了一个用来交换元素用的临时空间，不需要别的。

那么，能不能更给力点呢？

可以。

我们假定12所在的位置就是正确位置；然后分头往左右两侧查找。比如左侧发现更大的，那么就到右侧找一个更小的交换——如此反复，很快就会有一侧先找到头了（假设是左侧，右侧同理）。

现在，只要在右侧找到一个更小的，把它放在12所在的位置；再把12右侧第一个元素放到这个数字原来占用的位置——如此反复，很快就能完成排布了。

注意，12可以先存在临时空间，这样就不需要每次移动位置就多一次交换了。

最终，这个方法多占用了一个临时存储单元，但只需N次比较、次数和位置不正确的元素数相当的若干次交换——这个效率显然已经优化到了极致：你不可能比它少比较一次、也不可能比它少交换一次。

你看，算法效率有没有达到极致也是可以分析甚至证明的，一点都不虚无缥缈。

事实上，现在的qsort算法之所以如此精简高效，恰恰是因为编写它的人早已把这套分析法学成了本能、一字一句全都在它的指导下进行——不存在半点运气因素。

科学技术就是这么残酷。会就是会，不会就是不会。会的人一出手就是最高效率，不会的人……挣扎大半年，基本功能都写不对。

当然，对于更复杂的算法、或者结合特定的机器结构，它的优化空间可能要比这个大得多；加上数据不同的排布概率造成的影响，这个证明可能很困难、甚至超出了我们的数学/思想水平。

但要证明这个同样困难，远比证明一个算法已经优化到极致困难：恰恰相反，当一个算法无法证明已经优化到极致时，很可能是我们掌握的数学知识还不够多；换一个更强的人，他可能一出手就能把它优化到极致。因为在掌握了更强数学思想的人那里，解决方案是如此显然、如此清晰。

无论如何，学会自己证明算法是否达到了最优化，这是万里长征的第一步。只有掌握了这种分析能力，算法效率才能像掌上观纹一样清晰——最最起码，你会马上知道，我这个实现很粗糙、还有很大的优化空间。

最最起码你也要知道，那些“自己不会所以别人都不应该会”的人是注定的庸人。因为他的思想早早封闭了。

恰恰相反，正因为人外有人天外有天，这个世界才显得如此精彩。