c++ - 排序优化时间

Question

我有两种:

void sort1(std::vector<int> &toSort)
{
    for(VintIter i=toSort.begin(); i!=toSort.end(); i++)
    {
        for (VintIter j =(toSort.end()-1); j != i; --j)
        {
            if (*(j - 1) > *(j))
            {
                std::iter_swap(j - 1, j);
            }
        }
    }
}

 void sort2(std::vector<int> &toSort)
    {

        for(int i= 0; i<(toSort.size()-1); i++)
        {
            int minElem=i,maxElem=i+1;
            if(toSort[minElem]>toSort[maxElem])
            {
                std::swap(toSort[minElem],toSort[maxElem]);
            }

            while(minElem>0 && toSort[minElem]<toSort[minElem-1])
            {
                std::swap(toSort[minElem],toSort[minElem-1]);
                minElem--;
            }

            while(maxElem<(toSort.size()-1) && toSort[maxElem]>toSort[maxElem+1])
            {
                std::swap(toSort[maxElem],toSort[maxElem+1]);
                maxElem++;
            }

        }

    }

我正在使用 QueryPerformanceFrequency 和 QueryPerformanceCounter 来获取这些时间。 对于 1000 个元素的随机 vector ，sort1 返回 20.3，sort2 返回 5.4。这没关系.. 但是当我试图获得排序数组的结果时，所以对于 toSort vector 已经排序的最佳情况，结果有点奇怪.. 对于 sort1 它是 12.234 而对于 sort2 是 0.0213.. 对于 10 000 个元素，sort1 为 982.069，而 sort2 为 0.2!

如果 vector 已排序，我有断言用于比较。 我在 Windows 7 和 Windows 8 上使用最新的 mingw。对于 i7-5700 HQ 和 i5-6300U..

这只是我创造更好的东西的练习，没有实现。我都是关于我的想法，所以我不想使用 std::sort。

我的问题是: 为什么第二种算法在 10 000 个元素的情况下给出 ~0 时间？

Answer 1

第一个复杂度为 n²无论如何。

而在排序的情况下，您的第二个算法是线性的:

toSort[minElem] < toSort[minElem - 1]和 toSort[maxElem] > toSort[maxElem+1]总是 false , 所以你的内部循环立即中断。