algorithm - 快速排序时间复杂度最佳案例输入

Question

我必须在 C 程序中找到最佳案例输入的快速排序的时间复杂度，并且我已选择数组的最后一个元素作为主元。 现在我知道在最佳情况下我必须输入什么输入值，即，将第一个中间元素保留在最后一个位置(枢轴)，下一个枢轴应该是下一个中间元素。 但是我必须生成这种非常大的最佳情况输入数组，例如 1000、5000、100000..，以便快速排序。 我可以编码，但任何人都可以帮助我了解如何使用 c 编程生成那种最佳情况输入数组，以便使用最后一个数据透视表进行快速排序。 我只需要逻辑，例如如何使用 C 编程生成那种数组。

Answer 1

基本上，您需要采用类似于快速排序本身的分而治之方法。使用在输出中给出一系列索引的函数来执行此操作:

1. 通过递归调用自身生成上半部分

2. 通过递归调用自身生成后半部分

3. 在下半部分之后插入枢轴值。

需要注意的一件事是，由于您只是生成输出而不对任何内容进行排序，因此您实际上不必将任何值作为输入——您可以将范围逻辑地表示为数组中某个索引处的起始值，然后一个计数。

下面是一些C#代码；这是未经测试的——如果您想自己做，请不要看。

static int[] GenerateBestCaseQuickSort(int n)
{
    var ary = new int[n];
    GenerateBestCaseQuickSortAux(ary, 0, n, 1);
    return ary;
}

static void GenerateBestCaseQuickSortAux(int[] ary, int start_index, int count, int start_value)
{
    if (count == 0)
        return;

    if (count == 1)
    {
        ary[start_index] = start_value;
        return;
    }

    int partition1_count = count / 2;
    int partition2_count = count - partition1_count - 1; // need to save a spot for the pivot so -1...
    int pivot_value_index = start_index + partition1_count;
    int pivot_value = start_value + partition1_count;

    GenerateBestCaseQuickSort(ary, start_index, partition1_count, start_value);
    GenerateBestCaseQuickSort(ary, pivot_value_index, partition2_count, pivot_value+1);
    ary[start_index + count - 1] = pivot_value;
}