因为资讯有限，我没有办法做完整的判断， 所以我只针对各段独立的做回覆。 ※ 引述《sudada (叽咕叽咕叽咕)》之铭言： : 各位好 : 最近遇到一个sorting的问题 : 假设我有一个List里面放我自订的class : 他必须是个排序好的状态 : 但是每次有新增或更新资料 我都必须取得那笔资料的index 说不定该改进的是这个需求？ : 而且使用上get range的使用机率应该会比insert高一点 : 目前我有两种想法 : 第一 : 每次丢资料进去都call一次sort : 不过这样没办法直接知道我刚刚新增的那笔资料 : 到底会被丢到哪里去 : 所以sort完以後还要再抓一次index? : 这种方法我觉得完全不可行...... : 第二 : 跑回圈用自己的compare方式找到适当的位置 : 直接call insert : 这样"感觉上"快很多 : 但是问题出在用List的资料结构的话 : 每次都必须从头开始 cost应该是O(n)? List 是一种 ADT，而不是一种资料结构， 我想你指的应该是 ArrayList 或着 LinkedList 其中之一。 如果你指的是 ArrayList， 那麽在寻找插入点时可以用 binary search，而不需要 "从头开始"， 但是插入的部份要将所有 element 向後移，所以整体仍是 O(n)。 若指的是 LinkedList， 则是 O(n) 循序的找到插入点，并以 O(1) 完成插入， 但是每次 get 也都要 O(n)， 以你的需求来说，应该不会是个好选择。 : 如果要改进这里势必要改资料结构 : 用binary tree又怕会影响整体get的效能 : 想请问大家会怎麽取舍 : 谢谢 简单的说，ArrayList 就是 get O(1)，insert O(n) tree-based 的资料结构则都是 O(log n)， 若把 "get/insert 的比例" 及 n 代入，大概就可以看出哪一个选择比较有优势了。 --- 至於该不该做最佳化，那又是另一个议题了。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.34.7.189