堆排序CPU时间

Question

我已经在c++中实现了Heapsort，它确实对数组进行了排序，但是给了我比预期更多的CPU时间。它应该花费nlog(n)触发器，而且排序速度至少要快于bubblesort和插入排序。

相反，它给了我比bubblesort和插入排序更高的cpu时间。例如，对于ints的随机数组(大小为100000)，我有以下cpu时间(在nanoSeconds中)：

• BubbleSort: 1.0957e+11
• InsertionSort: 4.46416e+10
• MergeSort: 7.2381e+08
• HeapSort: 2.04685e+11

这就是守则本身：

   #include <iostream>
    #include <assert.h>
    #include <fstream>
    #include <vector>
    #include <random>
    #include <chrono>
    using namespace std;

    typedef vector<int> intv;
    typedef vector<float> flov;
    typedef vector<double> douv;


        void max_heapify(intv& , int);
        void build_max_heap(intv& v);

        double hesorti(intv& v)
        {
            auto t0 =chrono::high_resolution_clock::now();
            build_max_heap(v);
            int x = 0;
            int i = v.size() - 1;
            while( i > x)
            {
                swap(v[i],v[x]);
                ++x;
                --i;
            }
            auto t1 = chrono::high_resolution_clock::now();
            double T = chrono::duration_cast<chrono::nanoseconds>(t1-t0).count();
            return T;
        }
        void max_heapify(intv& v, int i)
        {
            int left = i + 1, right = i + 2;
            int largest;
            if( left <= v.size() && v[left] > v[i])
            {
                largest = left;
            }

            else
            {
                largest = i;
            }

            if( right <= v.size() && v[right] > v[largest])
            {
                largest = right;
            }

            if( largest != i)
            {
                swap(v[i], v[largest]);
                max_heapify(v,largest);
            }



        }

        void build_max_heap(intv& v)
        {
            for( int i = v.size() - 2; i >= 0; --i)
            {
                max_heapify(v, i);
            }

        }

Answer 1

堆排序的实现肯定存在问题。

查看hesorti，您可以看到它只是在调用build_max_heap之后逆转了向量的元素。因此，build_max_heap不只是在做堆，它实际上是对整个数组进行反向排序。

max_heapify已经有了一个问题:在堆的标准数组布局中，数组索引I处节点的子节点不是i+1和i+2，而是2i+1和2i+2。这是干什么用的？

当第一次调用它时，在最后两个元素上(当i=n-2)，它只需确保越大越小。在那之后叫它会发生什么呢？

让我们来做一些数学归纳。对于所有j>i，在调用数组上索引j的max_heapify之后，从vj+1到vn-1的数字已经按降序排列，结果是从vj到vn-1的数字按降序排序。(我们已经看到，当我=n-2时，这是真的。)

如果vi大于或等于vi+1 (因此也等于vi+2 )，则不会发生掉期，当max_heapify返回时，我们知道从i到n-1处的值是降序的。在另一个案子里会发生什么？

在这里，largest设置为i+1，根据我们的假设，vi+1大于或等于vi+2 (事实上，对于k>i+1的所有vk )，因此针对'right‘索引(i+2)的测试永远不会成功。vi与vi+1交换，使vi成为从vi到vn-1的最大数字，然后对从i+1到结尾的元素调用max_heapify。通过我们的归纳假设，这将对这些元素进行降序排序，因此我们知道，现在从vi到vn-1的所有元素都是降序的。

通过归纳的力量，我们证明了build_max_heap将反向排序元素。这样做的方式，是依次渗透元素，从后面工作，进入它们在后面的反排序元素中的正确位置。

这个看起来眼熟吗？这是插入排序！但是它是反向排序，所以当调用hesorti时，交换序列将它按正确的顺序排列。

插入排序也有O(n^2)的平均行为，这就是为什么您得到的数字与气泡排序相似。由于插入步骤的复杂实现，它的速度几乎肯定较慢。

TL;DR:您的堆排序并不快，因为它实际上不是堆排序，而是向后插入排序，然后是就地顺序反转。