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

Question

我正在尝试向我的快速排序算法添加一个计数器，以显示在给定数组上执行的交换总数。但是，我运气不佳，并且生成了一个明显不正确的值 (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.820 1.810 1.790 1.750 1.780 1.850 1.790 1.790 1.780 1.770 1.760 1.770 1.670 1.610 1.610 1.590 1.540 1.520 1.510 1.540 1.620 1.600 1.560 1.570 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.610 1.560 1.580 1.570 1.630 1.640 1.720 1.750 1.750 1.680 1.610 1.620 1.600 1.570 1.510 1.530 1.520 1.550 1.550 1.670 1.650 1.540 1.560 1.710 1.860 1.830 1.670 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

这是代码

  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;
    }

已解决:通过引用传递了步骤值，现在按预期工作

Answer 1

有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);