向快速排序算法添加计数器以显示交换操作的总数

用户名

我正在尝试向我的quicksort算法添加一个计数器,以显示在给定数组上执行的交换总数。但是,我没有运气,并且正在生成一个明显不正确的值(14)。

被操纵的数组是“ arr”,它是128个十进制数字的集合;

1.960 2.010 2.020 1.940 2.030 2.050 2.000 1.890 1.860 1.960 1.990 2.010 2.010 2.010 1.960 1.940 1.920 1.930 1.980 1.960 1.940 1.900 1.860 1.890 1.860 1.860 1.860 1.820 1.810 1.790 1.750 1.780 1.850 1.790 1.790 1.780 1.770 1.770 1.760 1.770 1.770 1.670 1.610 1.610 1.590 1.540 1.520 1.510 1.540 1.620 1.600 600 1.470 1.420 1.440 1.410 1.450 1.370 1.340 1.320 1.330 1.430 1.440 1.430 1.470 1.480 1.510 1.570 1.630 1.680 1.720 1.710 1.670 1.650 1.620 1.620 1.610 1.560 1.580 1.570 1.630 1.640 1.720 1.750 1.750 1.750 1.680 1.610 1.620 1.600 1.5600 1.570 1.510 1.530 1.520 1.520 1.550 1.550 1.670 1.650 1.540 1.560 1.710 1.860 1.750 1.760 1.780 1.890 2.010 2.010 1.970 1.980 2.040 2.020 2.020 2.020 2.080 2.080 2.080 2.100 2.170 2.160 2.150 2.150 2.120 2.110 2.090 2.130 2.150 2.110 2.100 2.120 2.120

这是代码

  int n = arr.Length;
  int step = 0;
  int totalsteps = Quick_Sort(arr, 0, n - 1, step);
  Console.WriteLine("Number of steps = {0}", totalsteps);

 private static int Quick_Sort(decimal[] arr, int left, int right, int step)
    {
        int i, j;
        decimal pivot, temp;
        i = left;
        j = right;
        pivot = arr[(left + right) / 2];
        do
        {
            while ((arr[i] < pivot) && (i < right)) i++;
            while ((pivot < arr[j]) && (j > left)) j--;
            if (i <= j)
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
                step++;
            }
        } while (i <= j);
        if (left < j) Quick_Sort(arr, left, j, step);
        if (i < right) Quick_Sort(arr, i, right, step);
        return step;
    }

已解决:通过参考传递了步长值,现在可以按预期工作

一般

对此有3种可能的解决方案

返回值

private static int Quick_Sort(decimal[] arr, int left, int right)
{
   int step = 0;
   int i, j;
   decimal pivot, temp;
   i = left;
   j = right;
   pivot = arr[(left + right) / 2];
   do
   {
      while ((arr[i] < pivot) && (i < right)) i++;
      while ((pivot < arr[j]) && (j > left)) j--;
      if (i <= j)
      {
         temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
         i++;
         j--;
         step++;
      }
   } while (i <= j);
   if (left < j) step += Quick_Sort(arr, left, j, step);
   if (i < right) step += Quick_Sort(arr, i, right, step);
   return step;
}

参考值

private static void Quick_Sort(decimal[] arr, int left, int right, ref int step)
{
   int i, j;
   decimal pivot, temp;
   i = left;
   j = right;
   pivot = arr[(left + right) / 2];
   do
   {
      while ((arr[i] < pivot) && (i < right)) i++;
      while ((pivot < arr[j]) && (j > left)) j--;
      if (i <= j)
      {
         temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
         i++;
         j--;
         step++;
      }
   } while (i <= j);
   if (left < j)  Quick_Sort(arr, left, j, ref step);
   if (i < right)  Quick_Sort(arr, i, right, ref step);

}

全局变量

private int _step= 0;

private static void Quick_Sort(decimal[] arr, int left, int right)
{
   int i, j;
   decimal pivot, temp;
   i = left;
   j = right;
   pivot = arr[(left + right) / 2];
   do
   {
      while ((arr[i] < pivot) && (i < right)) i++;
      while ((pivot < arr[j]) && (j > left)) j--;
      if (i <= j)
      {
         temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
         i++;
         j--;
         _step++;
      }
   } while (i <= j);
   if (left < j)  Quick_Sort(arr, left, j );
   if (i < right)  Quick_Sort(arr, i, right);
}

原始答案

您没有将结果step从递归添加回

if (left < j) step += Quick_Sort(arr, left, j, step);
if (i < right) step += Quick_Sort(arr, i, right, step);

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章