一个极奇怪的快速排序问题·

Question

我用arraylist添加一个50000个整形的int然后排序
仅计算其Sort所用的时间,仅耗时0.06秒左右
可是我自己写一个快速排序或者是调用array.sort的快速排序（根据反编译arraylist.sort里调用的也是array.sort），结果却要0.5秒左右时间··为何相差那么大？？
到底微软在arraylist里面搞了什么？

Answer 1

就算是加上arraylist.add元素的时间··也不超过0.1秒··

Answer 2

有时候arraylist更是恐怖的0毫妙
有那么厉害吗

Answer 3

首先，计算算法事件要取几十次计算的平均值，并且要注意程序运行环境、有没有i/o和网络的影响等等。其次，ArrayList的Sort实际上会调用Array类型的Sort，而这个Sort又会重新在两种类型中选一种创建数据集合 —— 一种针对引用类型一种另外一种值类型（大意如此，其实string也是引用类型，我这里所说的值是所占的位置很短、不需要指针引用的）。其中，针对引用类型的，在比较两个元素的时候会根据object指针去找对象，然后调用对象的compare接口去比较大小；针对值类型的，在比较元素的时候会去直接使用针对值大小比较的接口。在挪动元素的时候，引用类型会挪动指针，而值类型的元素由于占用的位置很短，直接交换他们的指而不用去寻找指针。注意，ArrayList中虽然写入的int类型的数据被装箱为object了，但是 sort 算法此时首先将整个集合复制为不需要拆箱装箱的新的Array然后排序。而你自己写的ArrayList的排序算法，可能只是单纯对ArrayList中的数据读写，此时每一个动作都对数据不断反复拆箱装箱。最后，你调用Array的Sort与ArrayList调用Array的Sort的入口参数一样吗？

Answer 4

时间很短很正常。当数据已经几乎排好序了，那么排序其实就是一些比较而并不会大量地搬动元素。QuickSort作了一些必要的优化。
1. 在划分元素的时候它对已经排好序的集合反而处理的很快，而理论上的的快速排序算法对已经排好序的几乎反而是所有排序算法中最慢的。
2. 划分之后，首先选择小的集合进行递归。这样将递归深度减小——对函数栈的存储减到最小，可以尽快结束递归。
3. 尾递归转化为迭代循环，根本不用递归，不消耗函数栈。你的算法又是怎么做的呢？

Answer 5

我自己写的算法：
public static void QuickSort(IList oArray,int iStart,int iCount,IComparer oComparer)
{
if (iCount>1)
{
int i=iStart;
int j=iStart+iCount-1;
object oTemp=oArray[iStart];
do
{
while(i<j && oComparer.Compare(oTemp,oArray[j])<=0)
--j;
if (i<j)
{
oArray[i]=oArray[j];
++i;
}
while(i<j && oComparer.Compare(oArray[i],oTemp)<=0)
++i;
if (i<j)
{
oArray[j]=oArray[i];
--j;
}
}while(i<j);
oArray[i]=oTemp;
QuickSort(oArray,iStart,i-iStart,oComparer);
QuickSort(oArray,i+1,iStart+iCount-i-1,oComparer);
}
}调用array.sort的代码：
Array.Sort(array,null,0,array.Length,c);

Answer 6

你的算法就没有我说的任何一种优化。它使用object类型，比较时不断装箱拆箱操作。oTemp 的赋值没有对几乎已经排过序的段落进行优化。递归调用 QuickSort 时没有首先选择最浅的那一个，而是固定的顺序。最后一个 QuickSort 没有改为循环迭代。