Java QuickSort最佳案例数组生成 [英] Java QuickSort Best Case Array Generation

问题描述

我一直在这上面敲桌子.

I've been banging my head on the table on this one.

我需要创建一个针对QuickSort分区进行了优化的n大小的数组.它将用于演示QuickSort最佳案例的发展.我知道，在最佳情况下，QuickSort必须选择一个枢轴，以便为每个递归调用将数组分成两半.

I need to create an n sized array that is optimized for QuickSort Partition. It will be used to demonstrate the growth of QuickSort's best case. I know that for best case, QuickSort must select a pivot that divides the array in half for every recursive call.

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

I cannot think of a way to create an n-sized optimized array to test. Any help would be greatly appreciated.

这是Java中的算法.

Here is the algorithm in 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);
}

}

推荐答案

我知道这是一个老问题，但是我遇到了同样的问题，并最终提出了解决方案.我不是Java程序员，所以请不要怪我Java代码问题.我假设快速排序算法在分区时总是以第一项为枢纽.

I know this is an old question, but I had the same question and finally developed a solution. I'm not a Java programmer, so don't blame me for Java code issues, please. I assumed that the quicksort algorithm always takes the first item as a pivot when partitioning.

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个项目的数组产生相同的输出，如下所述:.如果有人需要用C ++解决方案:

This program produces the same output for the array of 15 items, as described here: An example of Best Case Scenario for Quick Sort. And in case someone needs a solution in 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);
}

这篇关于Java QuickSort最佳案例数组生成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！