给一道面试题，看看各位有什么建议。

Question

要求： 
  使用任何编程语言（java,c/c++,python,perl,etc），并且只能用一个长度为10的array/list对1000个数字排序。你能使用一些局部/临时变量，但不再是collection/list/array结构的。 实现情况： 
  工程能生成1000个随机数字，并打印结果和总共比较的次数。目标要求是比较次数最少。

Answer 1

这个题主要是考排序算法,应该是直接插入排序。下面是这个排序算法的代码，可以参考一下：
template <class record,class compare>
class straightinsertsorter:public sorter<record, compare>  //直接插入排序类
{ public:
void sort(record array[],int n)
{
int m=0, c=0;
for(int i=1;i<n;i++)
{
for(int j=i;j>0;j--)//依次与前面的纪录比较
{
c++;
if(compare::it(array[j],array[j-1]))  //array[j]<array[j-1]时为真
{   

swap(array,j,j-1);   //交换array[j],array[j-1]
m+=3;
}
else break;
}
}
cout<<"比较次数为:"<<c<<endl;
cout<<"移动次数为:"<<m<<endl;
}
};

Answer 2

下面是各种排序算法对同一数组排序的执行结果（这是程序的执行结果）
长度为10的随机数组为:1  7  4  0  9  4  8  8  2  4      //原来的数组
快速排序：
比较次数为:47
移动次数为:73
0  1  2  4  4  4  7  8  8  9            //排序后的结果
直接插入排序：
比较次数为:26
移动次数为:54
0  1  2  4  4  4  7  8  8  9         //排序后的结果
直接选择排序：
比较次数为:45
移动次数为:27
0  1  2  4  4  4  7  8  8  9       //排序后的结果
shell选择排序：
比较次数为:45
移动次数为:27
0  1  2  4  4  4  7  8  8  9       //排序后的结果
堆排序：
比较次数为:45
移动次数为:27
0  1  2  4  4  4  7  8  8  9        //排序后的结果
冒泡排序：
比较次数为:45
移动次数为:54
0  1  2  4  4  4  7  8  8  9   //排序后的结果
Press any key to continue