快速排序时间复杂度最佳案例输入 [英] Quick Sort Time Complexity Best Case Input

问题描述

我必须在c程序中找到用于BEST CASE INPUT的快速排序的时间复杂度；我选择了数组的最后一个元素作为枢轴.现在，我知道最佳情况下必须输入哪些输入值，即，将第一个中间元素保留在最后一个位置(枢轴)和?.下一个枢轴应该是下一个中间元素.但是我必须生成这种最佳情况的输入数组，该数组的大小非常大，例如1000、5000、100000 ..，以便进行快速排序.我可以编写代码，但是任何人都可以帮助我了解如何使用c编程来生成这种最佳情况的输入数组，以便在最后一个数据点进行快速排序.我只需要像这样的逻辑，即如何使用c编程来生成这种数组.

I have to find time complexity of quick sort for BEST CASE INPUT in a c program & i have selected the last element of array as pivot. Now i know what input values i have to enter for best case, i.e., keep 1st middle element at the last place(pivot) & next pivot should be the next middle element. But i have to generate this kind of best case input array of very big sizes like 1000, 5000, 100000.., for quick sort. I can code, but can anyone please help me understand how to generate that kind of best case input array for quick sort with last pivot, using c programming. I just need the logic like how to generate that kind of array using c programming.

推荐答案

基本上，您需要进行除法&征服类似于快速排序本身的方法.使用给定输出中的索引范围的函数来做到这一点:

Basically you need to do a divide & conquer approach akin to quicksort itself. Do it with a function that given a range of indices in the output:

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

1. generates the first-half partition by recursively calling itself

通过递归调用自身来生成后半分区

generates the second-half partition by recursively calling itself

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

inserts the pivot value after the second-half partition.

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

One thing to note is that since you are just generating output not sorting anything, you don't actually have to have any values as input -- you can just represent ranges logically as a start value at some index in the array and a count.

下面是一些C#代码；这未经测试-如果您想自己做，就不要看.

Some C# code is below; this is untested -- don't look if you want to do this yourself.

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

这篇关于快速排序时间复杂度最佳案例输入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！