命名排序算法。是快排吗？

Question

对于我写的这个排序算法，我有两个疑问：

1.When 我用范围填充向量 [max-num, 0]（最坏情况）我得到的结果比 O(n^2) 好得多。（我什至不确定我是否再写过快速排序）。

2.When 我混淆了范围，例如：我填充未排序的向量 [0, max-num/2] 然后 [max-num/2, 0]，奇怪的是它运行时崩溃了 900,000 但紧随其后崩溃。

template<class writeIter>
void quicksort(writeIter begin, writeIter end)
{
if (begin!= end) {
    int diff = end-begin;
    if (diff > 2) {

        writeIter pivot = ((end-begin) / 2) + begin;
        writeIter itFirst = begin;
        writeIter itSecnd = end-1;
        auto pivotVal = *pivot;

        swap(*pivot, *(end-1));
        while (itFirst < itSecnd) {
            if (*itFirst > pivotVal) {
                while (*itSecnd > pivotVal && itSecnd > itFirst) --itSecnd;
                if (itSecnd > itFirst)
                    swap(*itFirst, *itSecnd);
            }
            ++itFirst;
        }
        swap(*itSecnd, *(end-1));

        quicksort(begin, itSecnd);
        quicksort(itSecnd, end);
    }
    else if (diff  == 2)
        if (*begin > *(begin+1))
            swap(*begin, *(begin+1));
 }
}

Answer 1

是的，这是朴素的快速排序。但是你选择了中间元素而不是最后一个元素作为你的支点。

当你填充一个向量 [max-num, 0] 时，它实际上 不是最坏的情况。因为每次选择中间元素作为枢轴，将向量分为两部分几乎相同的大小，所以时间复杂度是 O(nlogn).
但是，当您填充未排序的向量 [0, max-num/2] 然后 [max-num/2, 0] 时，这对您的算法来说是最坏的情况，因为您将向量分成两部分一只极长一只极短。所以时间复杂度是O(n^2).

要在几乎所有向量上获得更好的性能，您可以：

选择一个随机元素作为你的支点
随机取三个元素，选第二大的
当向量的大小足够小，例如小于 10 时，对其应用插入排序
为了处理所有元素彼此靠近的情况，可以在递归排序子向量之前做一些额外的工作以跳过等于主元的元素

命名排序算法。是快排吗？

Naming the sorting algorithm. Is it QuickSort?

c++

sorting

quicksort