用哪种数据结构、算法更快

我有这样一个需求，要对一组integer数据大约250个，进行排序，这些数据经常被更新大约十几二十个，而其他的保持不变，但是这种更新非常频繁，而且我需要读更新之后的前面一些结果和结果所对应的索引。前面问过类似的问题，版主也回答过，使用linq的方式，排序倒是非常快，可是在我读取结果之后，速度竟然和使用array.sort之后读取速度一样了。

举个例子来说，在之前操作后有这样一组数据，
索引：0,1,2,3,4,5,6,7,8,9
数据：9,8,7,6,5,4,3,2,1,0
现在将输入改变后，结果如下
索引：0,1,2,3,4,5,6,7,8,9
数据：9,8,7,6,5,4,3,2,9,9
这时， 我要得到按数据从大到小排序的索引，并且要访问其中的一部分（确切说是从0索引开始访问排在前面的一部分） 数据。

可以看出，当后续索引和数据读取后，下次操作前数据处于有序状态，也就是说， 数据被更新后进行本次排序前大部分还是有序的，用哪种方式效率更高呢？

st mytpe
dim val as integer
dim left as integer
dim right as integer
end st
dim mt(250) as st

这样的结构？使用插入式排序？

10 个解决方案

#1

http://msdn.microsoft.com/zh-cn/library/ms132319(v=vs.80).aspx

#2

现成的类都是按键排序的吧，我要按值排序键，而且我的值肯定要有重复的时候，最典型的就是初始值全部为0，所以不能键值互换。

#3

有可以反射这个源码的？参考一下倒是也可以。

#4

引用 1 楼 sp1234 的回复:

http://msdn.microsoft.com/zh-cn/library/ms132319(v=vs.80).aspx

没错。要说到是什么数据结构，那就是binary search tree，事实上sortedlist内部就是使用了binary search tree。

#5

怎么回事？


我要按value排序key

#6

引用 5 楼 zcsor 的回复:

怎么回事？


我要按value排序key

你可以为SortedList传递一个自定义的IComparer，去比较key。不过我认为这种情况下，自己实现一个bst，硬编码比较的过程效率更高。

#7

250个int排序，对效率有要求么？无论换什么算法，总耗时都不会有多大改变吧。

#8

额，，，我要在一秒钟之内完成十几万次递归……用array.sort(arr1(),arr2())占去了15%的时间……当我优化了其他部分的代码之后，占用时间达到了40%…………

#9

哎，不行就链式插入排序算法吧，就是不知道实现之后到底和现在比差多少

#10