求个按key排序value的【快速】算法
本帖最后由 zcsor 于 2012-12-16 21:07:04 编辑 我有两个长度相等的数组
key: 0, 120, -100, 97, 66, 66, 34, 2, -1024, 0……
val: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9……
按KEY（有相等的）对VALUE进行排序，要求是：
0、最好是快速排序算法，不要冒泡啊之类慢的，接口啊之类类库实现的。
1、KEY数组不要变，仅要VALUE按KEY排序的结果。
2、有阀值，也就是说，当KEY小于一定程度时，例如0，那么0，-100，-1024对应的VALUE的元素0,2,8,9放在排序结果之后（可以不是0,2,8，9这个顺序），最好返回排序结果中从哪个元素开始小于阀值。
3、KEY相等时，谁在前都可以。
就上面的key和val，若阀值为0则排序结果应该是（key不变的）：
val: 1, 3, 4, 5, 6, 7, 0,2,8,9 （返回小于阀值的位置为5或6，也就是7或0所在的位置额，数组下标为1的语言的话就是小于阀值位置为6或7）
越快越好…………额，代码和代码速度都是O(∩_∩)O~
另外问一个问题是否可能有解决方法：（如果有开个新帖子）
我把一组数据均为数字（为了看清楚，下标标记在上面）
下标：0,1,2,3,4,5,6,7,8,9
数据：A,B,C,D,E,F,G,H,I,J（用字母代替数据，其实与算法无关吧）
分成若干段
0,1,2,3,4,5,6,7
A,B,C,D,E,F,G,H
0,1,2,3,4,5,6,7
B,C,D,E,F,G,H,I
0,1,2,3,4,5,6,7
C,D,E,F,G,H,I,J
就是把10长度的数组用3个8长度的表示（其实我也很无奈），在我进行一些运算之后，会导致某些段的值发生变化（可能不变，但至少有变化的），这时我要把它们再合起来，合起来时要求每一位上取最大的。例如某次变化导致所有B变成K，而第一段的E变成了Z，第二段的E变成了Y，其他的不变。
0,1,2,3,4,5,6,7
A,K,C,D,Z,F,G,H
0,1,2,3,4,5,6,7
K,C,D,Y,F,G,H,I
0,1,2,3,4,5,6,7
C,D,E,F,G,H,I,J
这时我要重新合成起来，由于Z>Y>E，所以最终合成结果是：
下标：0,1,2,3,4,5,6,7,8,9
数据：A,K,C,D,Z,F,G,H,I,J（用字母代替数据，其实与算法无关吧）
有没有可能采用特定结构和算法优化这个过程呢……
[解决办法]
准备一个key的copy数组，计为ck数组
使用一次快排交换把数据以阀值为界分为两段，交换的时候需要连带着交换val里的值
然后把阀值内的那一段进行快排
空间复杂有点高...
不知道有没有更好的方法...
[解决办法]
第一个问题，既然你打算用快速排序，那就用快速排序。只是每个元素有key和val两个属性。阀值问题，就使用一个静态变量记录最大数组下标（不是val）。
第二个问题，感觉限制的原因不明，即使提出方案也不一定能用上。
[解决办法]
如果你的数据分布范围小，只是数据量大而已的话
那么其实有比快排还快的办法。
分桶！～
