c++ - 堆排序 CPU 时间

Question

我已经在 C++ 中实现了 Heapsort，它确实对数组进行了排序，但是给我的 CPU 时间比预期的要长。它应该花费 nlog(n) 次触发器，并且它应该比冒泡排序和插入排序更快地对其进行排序。

相反，它给了我比冒泡排序和插入排序更高的 CPU 时间。例如，对于一个随机的整数数组(大小为 100000)，我有以下 cpu 时间(以纳秒为单位):

• 冒泡排序:1.0957e+11
• 插入排序:4.46416e+10
• 合并排序:7.2381e+08
• 堆排序: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 之后反转 vector 的元素。所以 build_max_heap 不只是堆，它实际上是对整个数组进行反向排序。

max_heapify 已经有一个问题:在堆的标准数组布局中，数组索引 i 处节点的子节点不是 i+1 和 i+2，但是 2i+1 和 2i+2。它从 build_max_heap 的数组后面调用。这是做什么的？

第一次调用它时，在最后两个元素上(当 i=n-2 时)，它只是确保较大的元素出现在较小的元素之前。之后调用它会发生什么？

让我们做一些数学归纳。假设，对于所有 j>i，在调用 max_heapify 后，在一个数组上使用索引 j，其中数字 v[j+1] 到 v[n-1] 已经按降序排列，结果是数字 v[j] 到 v[n- 1] 按降序排列。 (我们已经看到当 i=n-2 时这是真的。)

如果 v[i] 大于或等于 v[i+1](因此 v[i+2] 为好吧)，不会发生交换，当 max_heapify 返回时，我们知道 i 到 n-1 的值按降序排列。在另一种情况下会发生什么？

此处，largest 设置为 i+1，根据我们的假设，v[i+1] 大于或等于到 v[i+2](实际上是 k>i+1 的所有 v[k])，所以测试“正确”索引 (i+2) 永远不会成功。 v[i] 与 v[i+1] 交换，使 v[i] 成为 v 中最大的数字[i] 到 v[n-1]，然后 max_heapify 对从 i+1 到结尾。根据我们的归纳假设，这将按降序对这些元素进行排序，因此我们知道现在所有从 v[i] 到 v[n-1] 的元素都是降序排列。

然后通过归纳法，我们证明了 build_max_heap 将对元素进行反向排序。它的方法是依次渗透元素，从后面开始，到它们在它后面的反向排序元素中的正确位置。

这看起来很眼熟吗？是插入排序!除了它是反向排序，所以当 hesorti 被调用时，交换序列将它置于正确的顺序。

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

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