合并排序工作但删除元素c ++

Question

好吧，我把所有东西都弄乱了，找不到问题。我是 c++ 的新手，真的需要帮助。合并排序工作得很好，但由于某些奇怪的原因不会给出所有的值。使用递归合并排序可能会令人困惑，所以希望我能解决这个问题。谢谢！1

程序为运行时的输出。忽略冒泡排序：

这是图像的输入： {41, 18467, 6334, 26500, 19169, 15724, 11478, 29358, 26962, 24464, 5705, 28145, 23281, 16827, 9961, 491, 2995, 11942, 48=6, 5123}=[

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector <int> mergeSort(vector <int> data);

vector <int> merge(vector <int> arrayOne, vector <int> arrayTwo);

vector <int> dataList;

vector <int> dataListSorted;

int main()
{
    for (int i = 0; i < 20; i++)
    {
        dataList.push_back(rand());
    }

    int arrSize = dataList.size();
    cout << arrSize << endl;

    for (int i = 0; i < arrSize; i++)
    {
        cout << dataList[i] << " ";
    }
    cout << endl;


    dataListSorted = mergeSort(dataList);

    cout << "mergeSort" << endl;

    for (int i = 0; i < arrSize; i++)
    {
        cout << dataListSorted[i] << " ";
    }
    cout << endl;
}   


vector <int> mergeSort(vector <int> data)
{
    int arrSize = data.size();

    if (arrSize == 1)
    {
        return data;
    }

    vector <int> arrayOne;
    vector <int> arrayTwo;
    
    for (int i = 0; i < (arrSize / 2); i++)
    {
        arrayOne.push_back(data[i]);
        arrayTwo.push_back(data[i+arrSize/2]);
    }

    arrayOne = mergeSort(arrayOne);
    arrayTwo = mergeSort(arrayTwo);

   
    return merge(arrayOne,arrayTwo);
}
   
vector <int> merge(vector <int> arrayOne, vector <int> arrayTwo)
{
    vector <int> data;

    
    while (arrayOne.size() != 0 && arrayTwo.size() != 0)
    {
        if (arrayOne[0] > arrayTwo[0])
        {
            data.push_back(arrayTwo[0]);
            arrayTwo.erase(arrayTwo.begin());
        }
        else
        {
            data.push_back(arrayOne[0]);
            arrayOne.erase(arrayOne.begin());
        }
    }

    while (arrayTwo.size() != 0)
    {
        data.push_back(arrayTwo[0]);
        arrayTwo.erase(arrayTwo.begin());
    }
    while (arrayOne.size() !=  0)
    {
        data.push_back(arrayOne[0]);
        arrayOne.erase(arrayOne.begin());
    }

    return data;
    

    
}

Answer 1

循环

for (int i = 0; i < (arrSize / 2); i++)
{
    arrayOne.push_back(data[i]);
    arrayTwo.push_back(data[i+arrSize/2]);
}

当 arrSize 为奇数时，

无法正常工作。例如，如果 arrSize 为 5，则 arrSize / 2 的计算结果为 2。然后，i 取值 0 和 1。因此，arrayOne 涵盖索引 0 和 1，并且 arrayTwo 涵盖索引 0+2=2 和 1+2=3。索引 4 被遗漏。

您可以通过添加条件检查或使用两个循环来修复它。例如，您可以在循环后添加

if (arrSize % 2 == 1) {
    arrayTwo.push_back(data[arrSize-1]);
}

更好的是，您可以数组。也就是说，您可以删除循环并使用：

arrayOne = vector<int>(data.begin(), data.begin()+arrSize/2);
arrayTwo = vector<int>(data.begin()+arrSize/2, data.end());

合并排序工作但删除元素c ++

Merge sort working but deleting elements c++

c++

sorting

mergesort

vector