测试用例是随机生成的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;
        }