百科问答小站 logo   百科问答小站
问题

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

回答
好的，咱们来聊聊怎么给一堆数字变个“魔术”，让它们按照咱们指定的方式排个序。这可不是简单的从大到小或者从小到大那么简单，往往是带着点“心思”的。比如，咱们可能想让偶数在前，奇数在后，并且偶数内部也按大小排，奇数也一样；或者想把所有正数放在前面，负数放在后面，然后中间的零也排个序。总之，灵活得很。

设计这样的排序程序，关键在于咱们要给数字“设卡”或者“分组”，然后对每一组或者按照某种规则来安排它们的位置。这就像咱们整理房间，先把衣服按颜色分一堆，裤子分一堆，然后每堆里再按长短或者款式整理。

下面我来给你掰扯几个思路，咱们就把它们叫做“排序策略”吧，比算法听起来更生动点：

策略一： 两路进发，分区先行

这个策略，就像咱们在马路上修路，先把能走的车辆分流开，再处理剩下的。

核心思想： 先根据一个“主干道”的规则把数字分成几大类，然后对每一大类内部再进行细致的排序。

具体操作：

1. 设定“分界线”规则： 咱们得先想清楚，是以什么为标准来区分数字？比如，是奇偶性？正负性？还是在某个范围内的值？
例子1：偶数在前，奇数在后，各自内部有序。
分界线： 数字是偶数还是奇数。
第一步（分区）： 咱们可以找两个“指针”或者说“游标”，一个从最前面开始（咱们叫它 `left`），一个从最后面开始（咱们叫它 `right`）。
`left` 往前走，直到它找到一个奇数。
`right` 往后退，直到它找到一个偶数。
一旦 `left` 指向奇数，`right` 指向偶数，并且 `left` 在 `right` 的前面，咱们就把这两个数字“对调”（交换位置）。这样，偶数就跑到前面去了，奇数往后去了。
然后，`left` 继续往前，`right` 继续往后，重复这个过程，直到 `left` 和 `right` 相遇或者交错。
第二步（内部排序）： 分完区之后，咱们就有了两个子区域：前面是偶数区，后面是奇数区。现在，咱们就可以对这两个子区域分别应用我们熟悉的排序算法了，比如冒泡排序、选择排序、插入排序，甚至是更高效的快速排序或归并排序。

例子2：正数在前，负数在后，零在中间，各自内部有序。
分界线： 数字是正数、负数还是零。
第一步（分区）： 这个会稍微复杂一点，可能需要两趟或者更精巧的设计。
方案 A（两趟）：
第一趟：处理正负。找一个指针从前到后，找一个从后往前。前面找负数，后面找正数，把它们交换。这样就把正负分开了，负数在前面，正数在后面。
第二趟：处理零。如果需要把零放在正数和负数中间，那可以再进行一次分区，把负数和零分一组，零和正数分一组。或者，更简单点，先完成正负分区，然后把负数区和正数区分别再处理零。
方案 B（三路快排思想）： 类似三路快排，咱们可以选一个“支点”（pivot），比如零。然后把所有小于零的挪到前面，所有大于零的挪到后面。最后在负数区和正数区内部再分别处理。
第二步（内部排序）： 分区完成后，对每个区间（负数区、零区、正数区）单独进行排序。

优点：

思路清晰： 先分组再排序，逻辑分明，容易理解。
灵活性高： 可以根据不同的“分界线”规则来设计。
效率不错： 分区的过程通常是线性的（O(n)），而内部排序的效率则取决于我们选择的排序算法。

缺点：

可能需要额外空间： 如果分区操作不能在原地完成（例如需要临时存储），可能会占用一些内存。
多次遍历： 有时为了完成分区，可能需要多次遍历数组。

策略二： 染色标记，一次到位

这个策略，有点像给群众发不同颜色的帽子，让他们自动站到各自的队伍里去。

核心思想： 遍历一次数据，同时给每个数字“染色”或打上标记，表明它应该属于哪个组，然后根据颜色来安排最终的顺序。

具体操作：

1. 预设“颜色”或“组别”： 确定数字可能属于哪些类别，并且给每个类别一个“编号”或“颜色”。
例子：排序 0, 1, 2 三种颜色（荷兰国旗问题）。
颜色： 0（比如代表负数或偶数）、1（比如代表零或特定范围的值）、2（比如代表正数或奇数）。
操作：
咱们需要三个指针：`low`（指向当前0区域的末尾）、`mid`（当前处理的元素）、`high`（指向当前2区域的开头）。
最初，`low` 和 `mid` 都指向开头，`high` 指向末尾。
循环处理 `mid` 指针指向的元素：
如果 `nums[mid]` 是 0：把它和 `nums[low]` 交换，然后 `low` 和 `mid` 都往前移一步。这意味着找到了一个0，把它放到0区域的末尾，并且 `mid` 现在指向下一个需要处理的元素。
如果 `nums[mid]` 是 1：它已经处在中间区域了，直接让 `mid` 往前移一步，继续处理下一个。
如果 `nums[mid]` 是 2：把它和 `nums[high]` 交换，然后 `high` 往后移一步。注意，这里的 `mid` 指针不动，因为被换过来的 `nums[mid]`（原来是`nums[high]`）我们还没有处理，它可能是0、1或者2，需要留在原地继续被 `mid` 处理。
循环继续，直到 `mid` 指针超过 `high` 指针。
结果： 数组会被分成三部分：前面是所有0，中间是所有1，后面是所有2。

优点：

一次遍历： 通常只需要对数据进行一次主要的遍历，效率很高。
原地操作： 很多这类算法可以实现原地排序，不需要额外的存储空间。

缺点：

规则受限： 这种方法更适合那种可以简单地进行三次（或更少）分区的场景。如果分类规则很复杂，或者需要很多个“颜色”，实现起来会比较困难。
理解门槛： 像荷兰国旗问题这种，初次接触可能需要花点时间理解指针的移动逻辑。

策略三： 分而治之，递归排序

这个策略，就像把一个大问题分解成几个小问题，把小问题解决了，大问题也就解决了。

核心思想： 将原问题分解成若干个规模较小但相似的子问题，递归地解决这些子问题，然后将子问题的解合并起来，形成原问题的解。

具体操作：

归并排序（Merge Sort）：
分解： 将数组分成两半。
治： 递归地对这两半进行排序。
合并： 将两个已经排好序的子数组合并成一个有序的数组。
如何应用于自定义排序？ 在“合并”这个步骤，咱们可以加入自定义的逻辑。比如，当合并两个子数组时，我们比较的是偶数和奇数，或者正数和负数。
例子：偶数在前，奇数在后，各自内部有序。
当合并两个有序的子数组 `left_half` 和 `right_half` 时：
咱们可以先遍历 `left_half`，把所有偶数都放到结果数组的前面。
然后，再遍历 `left_half`，把所有奇数放到结果数组的偶数后面。
接着，再遍历 `right_half`，把所有偶数放到前面。
最后，再遍历 `right_half`，把所有奇数放到后面。
这样就保证了在合并过程中，偶数优先被放到前面，并且在同类数字中保持了它们在子数组中的相对顺序。如果子数组内部已经按照我们想要的规则排序好了（比如偶数区内部有序，奇数区内部有序），那么合并后的结果就是我们想要的。

快速排序（Quick Sort）：
分解： 选择一个“支点”（pivot），将数组分成两部分：小于支点和大于支点。
治： 递归地对这两部分进行排序。
如何应用于自定义排序？ 在“分区”（partition）这个步骤，咱们可以修改支点的选择和比较逻辑。
例子：奇偶混合排序。
选择支点的时候，可以优先选择一个偶数作为支点（如果存在）。
分区时，我们不是简单地比大小，而是根据奇偶性和大小进行复合比较。比如，我们希望偶数排在前面。那么在分区时，一个偶数总是比任何奇数都要“靠前”。
更精细的例子： 如果我们想要 2, 4, 1, 3, 5 这样的排序，也就是说偶数在前，奇数在后，并且内部都按升序。
咱们可以把规则定义成：偶数 < 奇数。
在快速排序的分区函数里，比较两个数 `a` 和 `b` 的时候，这样判断：
如果 `a` 是偶数，`b` 是奇数，那么 `a` 应该在 `b` 前面（返回true）。
如果 `a` 是奇数，`b` 是偶数，那么 `a` 应该在 `b` 后面（返回false）。
如果 `a` 和 `b` 都是偶数，那么按照它们的值大小比较。
如果 `a` 和 `b` 都是奇数，那么按照它们的值大小比较。
这样，分区操作就会按照我们定制的规则来把数字“左右分开”。

优点：

高度递归和抽象： 能够处理非常复杂的排序需求，只要能把问题分解成子问题。
效率高： 像归并排序和快速排序本身就是非常高效的排序算法（平均时间复杂度 O(n log n)）。

缺点：

实现复杂度： 递归的实现有时会比较复杂，特别是对于初学者。
归并排序的额外空间： 归并排序通常需要额外的空间来存储合并过程中的临时数组。

如何选择适合你的策略？

1. 明确你的排序要求： 这是最关键的一步！你的数字需要满足什么条件？分成几类？每一类内部怎么排？
2. 评估复杂度：
如果你的排序要求很简单，比如只有两类（奇偶、正负），并且只需要把它们分开再各自排序，那么策略一（两路进发） 或者 策略二（染色标记） 可能更直接、更高效。
如果你的排序要求比较复杂，涉及到多层级的排序规则，或者需要比较两个数在排序中的“相对优先级”，那么策略三（分而治之），特别是修改快速排序或归并排序的比较逻辑，会更强大和灵活。
3. 考虑实现难度： 有些策略（如荷兰国旗问题）虽然高效，但初次实现可能需要仔细推敲。选择你最容易理解和实现的方法。
4. 关注资源限制： 如果内存受限，那么优先选择原地排序的算法（如原地分区 + 原地排序）。

一个小建议：

在开始编写代码之前，最好先用纸笔模拟一下你的算法。选取一小组数据，一步一步地走流程，看看是否能得到你想要的结果。这样可以避免很多逻辑上的错误。

总的来说，给数字变个花样排序，就像给它们量身定制一套“舞步”。关键在于理解它们的“个性”和“喜好”，然后设计出最适合它们的编舞方式！希望这些思路能帮到你！

网友意见

user avatar

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


首先分析它的复杂度。

这道题本质上要求知道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算法之所以如此精简高效，恰恰是因为编写它的人早已把这套分析法学成了本能、一字一句全都在它的指导下进行——不存在半点运气因素。

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


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

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

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


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

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

类似的话题

本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有

服务条款
联系我们
关于我们
隐私政策
友情链接
知乎
百度问答
搜狐
新浪