0

毫无疑问，数组大小为 5000、4998 次比较。[32] = 30 次比较等。

（针对不同的条件进行编辑：）对于奇数大小的数组相同：[35] 计数为 33。

我可以继续下去。

为什么是这样？Var 是 qcount。

我不相信分区中有任何比较，尽管也许我错了。我的同学有时会得到大约 80 倍的数字，所以我们的计数存在巨大差异。

我的代码虽然有效。所以这很好。只是数量差别很大。

谢谢阅读。所以当我真的不需要时，让我写得更多。 

public class QuickSortTest
  {

static int numcalls = 0;
static int qcount = 0;

public static void main(String[] args)
  {
    Random gen = new Random();
    int[] array = new int[5000];
    int i;
    for (i = 0; i < array.length; i++)
      {
        array[i] = gen.nextInt(5000) + 1;
      }
    System.out.println("Initial array:");
    for (i = 0; i < array.length; i++)
      {
        System.out.println(array[i] + " ");
      }
    System.out.println();
    quicksort(array, 0, array.length - 1);
    System.out.println("Sorted array:");
    for (i = 0; i < array.length; i++)
      {
        System.out.println(array[i] + " ");
      }
    System.out.println("Done!");
    System.out.println("qcount " + qcount);
  }

public static int partition(int stuff[], int a, int z)
  {
    int left = a, right = z;
    int saveStuff;
    int pivot = stuff[(a + z) / 2];

    while (left <= right)
      {
        while (stuff[left] < pivot)
          {
            left++;
          }
        while (stuff[right] > pivot)
          {
            right--;
          }
        if (left <= right)
          {
            saveStuff = stuff[left];
            stuff[left] = stuff[right];
            stuff[right] = saveStuff;
            left++;
            right--;
          }
      };
    return left;
  }

public static void quicksort(int stuff[], int a, int z)
  {
    int index = partition(stuff, a, z);
    if (a < index - 1)
      {
        quicksort(stuff, a, index - 1);
        qcount++;
      }
    if (index < z)
      {
        quicksort(stuff, index, z);
        qcount++;
      }
  }

}

4

0 回答 0