Java QuickSort 最佳案例数组生成

Question

我一直在用头撞 table 。

我需要创建一个 n 大小的数组，该数组针对快速排序分区进行了优化。它将用于演示 QuickSort 的最佳案例的增长。我知道在最好的情况下，QuickSort 必须为每个递归调用选择一个将数组分成两半的主元。

我想不出一种方法来创建一个 n 大小的优化数组来进行测试。任何帮助将不胜感激。

这是 Java 中的算法。

public class QuickSort {

private int length;

private void quickSort(int[] a, int p, int r) {
    if (p < r) {
        int q = partition(a, p, r);
        quickSort(a, p, q - 1);
        quickSort(a, q + 1, r);
    }
}

private int partition(int[] a, int p, int r) {
    int x = a[r];
    int i = p - 1;

    for (int j = p; j < r; j++) {
        if (a[j] <= x) {
            i++;
            exchange(a, i, j);
        }
    }
    exchange(a, i + 1, r);
    return i + 1;
}

public void exchange(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

QuickSort(int[] a) {
    if (a == null || a.length == 0) {
        return;
    }
    length = a.length;
    quickSort(a, 0, length - 1);
}

Answer 1

我知道这是一个老问题，但我有同样的问题并最终找到了解决方案。我不是 Java 程序员，所以请不要因为 Java 代码问题而责备我。我假设快速排序算法在分区时总是将第一项作为枢轴。

public class QuickSortBestCase
{
  public static void generate(int[] arr, int begin, int end)
  {
    int count = end - begin;
    if(count < 3)
      return;

    //Find a middle element index
    //This will be the pivot element for the part of the array [begin; end)
    int middle = begin + (count - 1) / 2;

    //Make the left part best-case first: [begin; middle)
    generate(arr, begin, middle);

    //Swap the pivot and the start element
    swap(arr, begin, middle);

    //Make the right part best-case, too: (middle; end)
    generate(arr, ++middle, end);
  }

  private static void swap(int[] arr, int i, int j)
  {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }

  private static void fillArray(int[] arr)
  {
    for(int i = 0; i != arr.length; ++i)
      arr[i] = i + 1;
  }

  private static void printArray(int[] arr)
  {
    for(int item : arr)
      System.out.print(item + " ");
  }

  public static void main(String[] args)
  {
    if(args.length == 0)
      return;

    int intCount = Integer.parseInt(args[0]);
    int[] arr = new int[intCount];

    //We basically do what quicksort does in reverse
    //1. Fill the array with sorted values from 1 to arr.length
    fillArray(arr);
    //2. Recursively generate the best-case array for quicksort
    generate(arr, 0, arr.length);

    printArray(arr);
  }
}

此程序为包含 15 个项目的数组生成相同的输出，如下所述:An example of Best Case Scenario for Quick Sort .如果有人需要 C++ 中的解决方案:

template<typename RandomIterator,
    typename Compare = std::less<typename RandomIterator::value_type>>
void generate_quicksort_best_case_sorted(RandomIterator begin, RandomIterator end)
{
    auto count = std::distance(begin, end);
    if (count < 3)
        return;

    auto middle_index = (count - 1) / 2;
    auto middle = begin + middle_index;

    //Make the left part best-case first
    generate_quicksort_best_case_sorted(begin, middle);

    //Swap the pivot and the start element
    std::iter_swap(begin, middle);

    //Make the right part best-case, too
    generate_quicksort_best_case_sorted(++middle, end);
}

template<typename RandomIterator,
    typename Compare = std::less<typename RandomIterator::value_type>>
void generate_quicksort_best_case(RandomIterator begin, RandomIterator end)
{
    {
        auto current = begin;
        RandomIterator::value_type value = 1;
        while (current != end)
            *current++ = value++;
    }

    generate_quicksort_best_case_sorted(begin, end);
}