具有一半大小帮助向量的归并排序

Question

我一直在尝试通过使用大小仅为需要排序的向量一半的帮助向量来优化合并排序实现。这应该是可能的，但我没有看到它。正常合并使用全尺寸帮助向量，在原始向量上有 2 个迭代器，一个从左侧站点开始，一个刚好在中间（如果向量大小是偶数，则过去）。

全尺寸帮助矢量合并

void TDMergeSort<T>::merge(vector<T>& v, int links, int midden, int rechts, vector<T>& hulp) const{
        int j = links;
        int li = links;
        int ri = midden;
        while (li < midden && ri < rechts) {
            if (v[li] < v[ri]) {
                hulp[j++] = v[li++];
            } else {
                hulp[j++] = v[ri++];
            }
        }

        while (li < midden) {
            hulp[j++]=v[li++];
        }
        while (ri < rechts) {
            hulp[j++]=v[ri++];
        }
    for(int i=links;i<rechts;i++){
        v[i]=move(hulp[i]);
    }
}

如何将其转换为 hulp 不是 v.size()，而是 v.size()/2 的版本？

Answer 1

有一次我用类似的方法解决了一个 HackerRank 问题（请参阅下面的适应你的方法）：

void merge(std::vector<int>& original, long long left, long long middle, const long long end) {
    const std::vector<int> leftSide({original.begin()+left, original.begin()+middle});
    const std::vector<int>& rightSide=original; // just to make the code clearer
    auto posForward=left;
    auto right=middle;
    // reset left offsets because we are using a new collection
    middle -= left, left = 0;
    for ( ; left < middle && right < end; ++posForward) {
        if (leftSide[left] <= rightSide[right]) {
            original[posForward] = leftSide[left++];
        } else {
            original[posForward] = rightSide[right++];
            // inversions += (middle-left); // info: removed for this SO answer
        }
    }
    while (left < middle) {
        original[posForward++] = leftSide[left++];
    }
    while (right < end) {
        original[posForward++] = rightSide[right++];
    }
}

你可以看到一个完整的程序here

适合您需要的代码：

void TDMergeSort<T>::merge(vector<T>& v, int links, int midden, int rechts, vector<T>& hulp) const {
    hulp = {v.begin()+links, v.begin()+midden};
    int j = links;
    int ri = midden;
    midden -= links;
    int li = 0;

    while (li < midden && ri < rechts) {        
        if (hulp[li] <= v[ri]) {
            v[j++] = hulp[li++];
        } else {
            v[j++] = v[ri++];
        }
    }

    while (li < midden) {
        v[j++]=hulp[li++];
    }
    while (ri < rechts) {
        v[j++]=v[ri++];
    }
}

具有一半大小帮助向量的归并排序

Mergesort with a half-sized help vector

c++

mergesort

适合您需要的代码：