测试用例是随机生成的10000个在0到1之间的随机数。
算法的执行时间我用StopWatch测的。
调用插入排序用时在300ms左右,而调用快速排序却要用到12000ms!!!!这是怎么回事?
我设置断点查看到排完序的数组,两个算法均没有问题。
快速排序是用递归写的,而插入排序没有递归,难道是C#调用系统堆栈很慢?
c#的内部机制我不太清楚,期待高手出来解答。
我把我的代码贴在下面:
public float[] Sort_Insert(float[] sequence, int low, int high)//插入排序
{
sorted = new float[sequence.Length];
sequence.CopyTo(sorted,0);
Stopwatch watch = new Stopwatch();//实例化跑马表
watch.Start();//开始计时
//-------------------
int i;
float temp;
for (int j = low + 1; j <= high; j++)
{
i = j - 1;
temp = sorted[j];
while (i >= low && sorted[i] > temp)//依次将j以前的元素后移一位
{
sorted[i + 1] = sorted[i];
i--;
}
sorted[i + 1] = temp;
}
//-------------------
watch.Stop();//计时停止
lbTime.Text = watch.ElapsedMilliseconds.ToString() + " ms";//得到运行的时间,毫秒级
return sorted;
}-------------------------------------------------------------
public float[] Sort_Quick(float[] sequence, int low, int high)//快速排序
{
sorted = new float[sequence.Length];
sequence.CopyTo(sorted, 0);
Stopwatch watch = new Stopwatch();//实例化跑马表
watch.Start();//开始计时
//-------------------
int pivot;//枢轴
if (low < high)
{
pivot = Partition1(sorted, low, high);
Sort_Quick(sorted, low, pivot - 1);
Sort_Quick(sorted, pivot + 1, high);
}
//-------------------
watch.Stop();//计时停止
lbTime.Text = watch.ElapsedMilliseconds.ToString() + " ms";//得到运行的时间,毫秒级
return sorted;
}
private int Partition1(float[] sequence, int low, int high)
{
float temp = sequence[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++)
{
if (sequence[j] <= temp)
{
i++;
Exchange(i, j);//交换两数
}
}
Exchange(i + 1, high);//交换两数
return i + 1;
}
算法的执行时间我用StopWatch测的。
调用插入排序用时在300ms左右,而调用快速排序却要用到12000ms!!!!这是怎么回事?
我设置断点查看到排完序的数组,两个算法均没有问题。
快速排序是用递归写的,而插入排序没有递归,难道是C#调用系统堆栈很慢?
c#的内部机制我不太清楚,期待高手出来解答。
我把我的代码贴在下面:
public float[] Sort_Insert(float[] sequence, int low, int high)//插入排序
{
sorted = new float[sequence.Length];
sequence.CopyTo(sorted,0);
Stopwatch watch = new Stopwatch();//实例化跑马表
watch.Start();//开始计时
//-------------------
int i;
float temp;
for (int j = low + 1; j <= high; j++)
{
i = j - 1;
temp = sorted[j];
while (i >= low && sorted[i] > temp)//依次将j以前的元素后移一位
{
sorted[i + 1] = sorted[i];
i--;
}
sorted[i + 1] = temp;
}
//-------------------
watch.Stop();//计时停止
lbTime.Text = watch.ElapsedMilliseconds.ToString() + " ms";//得到运行的时间,毫秒级
return sorted;
}-------------------------------------------------------------
public float[] Sort_Quick(float[] sequence, int low, int high)//快速排序
{
sorted = new float[sequence.Length];
sequence.CopyTo(sorted, 0);
Stopwatch watch = new Stopwatch();//实例化跑马表
watch.Start();//开始计时
//-------------------
int pivot;//枢轴
if (low < high)
{
pivot = Partition1(sorted, low, high);
Sort_Quick(sorted, low, pivot - 1);
Sort_Quick(sorted, pivot + 1, high);
}
//-------------------
watch.Stop();//计时停止
lbTime.Text = watch.ElapsedMilliseconds.ToString() + " ms";//得到运行的时间,毫秒级
return sorted;
}
private int Partition1(float[] sequence, int low, int high)
{
float temp = sequence[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++)
{
if (sequence[j] <= temp)
{
i++;
Exchange(i, j);//交换两数
}
}
Exchange(i + 1, high);//交换两数
return i + 1;
}
sequence.CopyTo(sorted, 0);
这是一个非常大的开销
10000个随机样本用快排只用5ms