作者LPH66 ((short)(-15074))
看板C_and_CPP
标题Re: [问题] 关於双层排序
时间Mon Apr 27 19:21:02 2009
※ 引述《suscym (DoDreamEr)》之铭言:
: 想了许久 都想不出乾净俐落的作法 ....
: 有可能是我本身的资料结构是array 不是动态 才比较麻烦
: ( 所以暂时不考虑改变资料结构)
: 今天我有一结构 里面有变数 帐户余额 和 年龄, 我先透过stable的排序法
: 依照帐户余额排列过(因为有可能余额同 所以我用stable的) 接着
: 我想在"资料已经依照余额由小到大排列过"的条件下,再进行年龄的排列
: 但是到目前为止 我只想出另外宣告一些资料结构 透过回圈不断检查 再把新顺序放在
: 新结构纪录,但是一直感觉这做法很没效率 又可能有逻辑上的漏洞... 所以想上来
: 请教各位的看法,谢谢
如果你要的是先对余额排 相同时再排年龄
以你这个方向有一个小修的做法
反过来先对年龄排序
然後再用 stable 的排序对余额排
这样就是你要的了
其原理嘛...有个排整数的 sort 法叫 Radix sort
这个方法是 LSB 先排的 Radix sort 的变形
以那里来类比 "十位" 相当於你的 "余额" (主要键)
"个位" 相当於你的 "年龄" (次要键)
这样就容易理解了
你之所以为碰壁是因为你做成了 MSB 先排的 Radix sort
这需要分别在每堆主要键相同的资料中对次要键来排
---
当然比较漂亮的做法是照原推文说的 比大小时直接就比出两笔资料的前後
这样一口气就可以把资料排好了
--
実琴:「
河野!你真的就这样被
物质慾望给吸引过去了吗?!」
亨:「只要
穿着女装摆出亲切的样子,所有必要花费就能
全免,似乎一点都不坏啊。」
実琴:「难道你没有
男人的尊严了吗?!」
亨:(断然道)「
没有。在
节衣缩食且
生活吃紧的
学生面前,
没有那种东西。」
--プリンセス・プリンセス 第二话
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.84
1F:→ suscym:真的很谢谢你耶 这MSB和LSB以前都学过 但是不大会活用 04/27 20:37
2F:→ suscym:没想到今天这两种关联变数的例子可以这样想 好强大!!! 04/27 20:37
3F:→ suscym:谢谢~!!! 04/27 20:37