C++ 堆排序算法在 4100 多个数据条目后崩溃？

Question

我已经开发了以下堆排序算法代码，但由于某种原因它在某个特定(大约 4100 区域)之前工作得很好，之后程序被迫关闭？

非常感谢任何帮助，谢谢。

void heap_from_root(MVector &v, int i, int n) {

    int end=n,j=0;

    // Identify the lowest root and how many sons it has. If it only has one son, set j=1.
    if (n==1) { n = 0; j = 1; }
    else if ((n-2) % 2 == 0) { n = (n-2)/2; }
    else if ((n-1) % 2 == 0) { n = (n-1)/2; j=1; }

    while (i <= n) { // Start from the lowest root, and go up until the highest root.

        if (j==0) { // If 2 sons, then check for the biggest value. If the biggest value is greater than root, exchange.

            if (v[2*n+1] > v[2*n+2] && v[2*n+1] > v[n]) { v.swap(2*n+1,n); }
            if (v[2*n+2] > v[2*n+1] && v[2*n+2] > v[n]) { v.swap(2*n+2,n); }

        }

        if (j==1) { // If 1 son, if the son's value is greater than the root, exchange.

            if (v[2*n+1] > v[n]) { v.swap(2*n+1,n); }
            j=0; // As only the last root can only have one son, set j to 0.

        }

        n--; // Go backwards to the next root.

    }

    /* The top value of the heap will now be the biggest value. If the heap hasn't been completed sorted, 
    put the biggest value at the END of the heap, and restart the algorithm, this time excluding that last 
    value. Repeating this recursively will mean the heap will be sorted in ascending order. This saves using
    significant excess memory. */

    if (i < end) { v.swap(i,end); end--; heap_from_root(v,i,end); }

}

void heap(MVector &v) { heap_from_root(v,0,v.size()-1); }

MVector 类是:

// class MVector contains arrays that can work with doubles
class MVector
{   
  // storage for the new vector class 
  vector<double> v;
  public:
    // constructor
    explicit MVector(){}
    explicit MVector(int n):v(n){srand(static_cast<unsigned>(time(NULL)));}
    explicit MVector(int n,double x):v(n,x){}
    // equate vectors;
    MVector& operator=(const MVector& X)
    {if(&X==this)return *this;v=X.v;return *this;}
    // access data in vector 
    double& operator[](int index){ return v[index]; }
    // access data in vector (const)
    double operator[](int index) const { return v[index]; }
    // size of vector
    int size() const {return v.size();}
    void push_back(double x){v.push_back(x);}
    void swap(int i,int j) { double c; c=v[i]; v[i] = v[j]; v[j] = c;  }
    void initialise_random(double xmin, double xmax) {
        const unsigned n = this->size();
        for(unsigned i=0;i<n;i++) {
            v[i] = xmin + rand()*(xmax - xmin) / static_cast<double>(RAND_MAX);
        }
    }

    bool cmp(int i, int j) { 
        if (v[i] < v[j]) { return true; } 
        else { return false; } 
    }
}; // end class MVector

它被发起

int main ()
{
    MVector x(4500);
    x.initialise_random(0,10);
    double y0 = timer();
    Sort::heap(x);
    double y = timer();

    std::cout << abs(y-y0) << endl;
}

Answer 1

不是答案，而是观察。你有这个代码:

if (n==1) { n = 0; j = 1; }
else if ((n-2) % 2 == 0) { n = (n-2)/2; }
else if ((n-1) % 2 == 0) { n = (n-1)/2; j=1; }

考虑当 n 为奇数时，n/2 == (n-1)/2。当 n 为偶数时，(n-1)/2 == (n-2)/2。因此，您可以将所有代码替换为:

if ((n % 2) == 1) { j = 1; }
n = (n-1)/2;