求整数对排序算法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求整数对排序算法

求整数对排序算法# JobHunting - 待字闺中

a*n2012-01-12 08:01

1 楼

不是面试题, 求整数对排序算法
我有一些整数对 { (1,4), (2,7), (1,5), (5,7), (5,9), (4,7) …}
最后排序成 {(1,5), (1,4), (2,7), (4,7), (5,9), (5,7) …}，具体是先按第一个数
字排升序，如果相同则按第二个数字怕降序，有没有有效的快速的算法。
谢谢了.

H*e2012-01-12 08:01

2 楼

没区别吧
就自己写一个比较函数好了

【在 a**n 的大作中提到】

: 不是面试题, 求整数对排序算法
: 我有一些整数对 { (1,4), (2,7), (1,5), (5,7), (5,9), (4,7) …}
: 最后排序成 {(1,5), (1,4), (2,7), (4,7), (5,9), (5,7) …}，具体是先按第一个数
: 字排升序，如果相同则按第二个数字怕降序，有没有有效的快速的算法。
: 谢谢了.

r*n2012-01-12 08:01

3 楼

1) sort them according the second number in decreasing order.
2) use stable sorting method(for example:insertion sort) to sort them
according the first number in increasing order.
average running time:O(nlogn)
if your integers fit in a short range, you can use counting sort,
it can be as fast as O(n) and space complexity is O(n).

【在 a**n 的大作中提到】

a*n2012-01-12 08:01

4 楼

不明白为什么要先sort第二个数，先sort第二个数有没有优点？

【在 r*******n 的大作中提到】

: 1) sort them according the second number in decreasing order.
: 2) use stable sorting method(for example:insertion sort) to sort them
: according the first number in increasing order.
: average running time:O(nlogn)
: if your integers fit in a short range, you can use counting sort,
: it can be as fast as O(n) and space complexity is O(n).

r*n2012-01-12 08:01

5 楼

this saves you from keeping track of many intermediate numbers the first
number of that are same.

【在 a**n 的大作中提到】

: 不明白为什么要先sort第二个数，先sort第二个数有没有优点？