高效率排序算法的一点补充
理论上，对于完全无序的大数组进行完整排序，效率最高的是快速排序。堆排序与快速排序具有相同数量级的运行时间，同样也是高效率的排序算法，但初始化堆可能要消耗大量时间，而且需要大量内存保存建立的堆。对于基本有序的数组，直接插入排序可能比快速排序效率更高，但若数组基本逆序时，效率极低。对于从大数组中选择少量数据，选择排序并不比快速排序或堆排序差。对于一些特殊的数组，使用非交换排序算法，可以突破O(nlogn)的限制。
归并排序，特别是多路归并排序，是很多操作系统做文件外排序采用的算法。它没有突破O(nlogn)，但可以极大地减少物理内存(即内存条)与虚拟内存(硬盘)之间的数据交换。若数组大到不能一次性全部装入内存时，它的实际运行效率高于快速排序。它的基本思想是这样：选择少量数据(比如说2 个或3个)为一组，内部用插入排序或选择排序(少量数据排序它们不慢)，然后将已排序的小组中选择2组或3组进行归并(将小组归并为大一点的组，使用选择排序效率就不错)，如此反复，直到组与整个输入数组一样大。
SHELL排序，其实质也是分组并行排序。在并行性好的高性能计算机上或者一个任务可由多台计算机同时运行的情况下，它比快速排序好。
基数排序，要求待排序数组具有可分类的性质。例如数组内全部是整数，先对个位数不同进行分类，再对十位数分类，这时可以利用个位已分类好的信息......若分类方法合适，基数排序效率可以好于O(nlogn)。
当然，楼主的要求应该属于查找的范围，若想扩展，将3扩大到n，如果n不很大，用选择排序就具有很高效率，理论值为O(n*ArraySize)，如果n很大，就该考虑快速排序或者堆排序，它们的效率为O(Arraysize*logn)。 “三个值好找……”，找到值时就记录循环指针的值，这不就是数组下标了吗？
页:
1
[2]