a**n
发帖数: 313 | 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***e
发帖数: 476 | 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*******n
发帖数: 3020 | 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 的大作中提到】
: 不是面试题, 求整数对排序算法
: 我有一些整数对 { (1,4), (2,7), (1,5), (5,7), (5,9), (4,7) …}
: 最后排序成 {(1,5), (1,4), (2,7), (4,7), (5,9), (5,7) …}，具体是先按第一个数
: 字排升序，如果相同则按第二个数字怕降序，有没有有效的快速的算法。
: 谢谢了.
| a**n
发帖数: 313 | 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*******n
发帖数: 3020 | 5 this saves you from keeping track of many intermediate numbers the first
number of that are same.
【在 a**n 的大作中提到】
: 不明白为什么要先sort第二个数，先sort第二个数有没有优点？
| b******v
发帖数: 1493 | 6 按你说的规则定义一个新的比较函数。然后用qsort按这个比较函数排序。O(n logn)
in average.
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 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) …}，具体是先按第一个数
: 字排升序，如果相同则按第二个数字怕降序，有没有有效的快速的算法。
: 谢谢了.
|
|
