排序优化时间

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 来获取这些时间。对于 sort1 returns 20.3 和 sort2 5.4 的 1000 个元素的随机向量。这没关系.. 但是当我试图获得排序数组的结果时，所以对于 toSort 向量已经排序的最佳情况，结果有点奇怪.. 对于 sort1 它是 12.234 而对于 sort2 是 0.0213.. 对于 10 000 个元素，sort1 是 982.069，sort2 是 0.2!

我有比较向量是否已排序的断言。我在 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，因此您的内部循环会立即中断。

排序优化时间

Sort Optimisation time

c++

sorting

query-performance