我正在尝试计算 100,000 个整数数组的合并排序过程中发生的反转次数。数组中的值没有特定的顺序。我的问题很简单,在合并排序算法中,我将在哪里应用反转计数器?下面是合并排序算法本身,之后的图像是我建议放置反转计数器的位置。文件读取正确并且合并排序工作正常,我只是问我的反转计数器的放置是否准确。任何建议将不胜感激!
清晰说明:主要区别位于 MergeSort 函数
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
void mergeSort(vector<int>&);
void merge(vector<int>&, vector<int>&, vector<int>&);
int main()
{
int size = 0, n, numValues = 0;
ifstream myFile;
myFile.open("IntegerArray.txt");
vector<int> array;
if (myFile.is_open())
{
while (myFile >> n)
{
array.push_back(n);
numValues++;
}
//for (int i = 0; i < 100000; i++)
//cout << array.at(i) << " ";
cout << "\nValues counted: " << numValues;
}
myFile.close();
mergeSort(array);
cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";
for (int i = 0; i < 100000; i++)
cout << array[i] << "\n";
}
void mergeSort(vector<int> &array)
{
if (array.size() <= 1) return;
int middle = array.size() / 2;
vector<int> left;
vector<int> right;
for (int i = 0; i < middle; i++)
left.push_back(array[i]);
for (int j = 0; j < (array.size() - middle); j++)
right.push_back(array[middle + j]);
mergeSort(left);
mergeSort(right);
merge(left, right, array);
}
void merge(vector<int> &left, vector<int> &right, vector<int> &array)
{
int leftSize = left.size();
int rightSize = right.size();
int i = 0, l = 0, r = 0;
while (l < leftSize && r < rightSize)
{
if (left[l] < right[r])
{
array[i] = left[l];
i++;
l++;
}
else
{
array[i] = right[r];
i++;
r++;
}
}
while (l < leftSize)
{
array[i] = left[l];
i++;
l++;
}
while (r < rightSize)
{
array[i] = right[r];
i++;
r++;
}
}
带有反转计数器的代码:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
void mergeSort(vector<int>&, int&);
void merge(vector<int>&, vector<int>&, vector<int>&, int&);
int main()
{
int size = 0, n, numValues = 0;
int numInversion = 0;
ifstream myFile;
myFile.open("IntegerArray.txt");
vector<int> array;
if (myFile.is_open())
{
while (myFile >> n)
{
array.push_back(n);
numValues++;
}
//for (int i = 0; i < 100000; i++)
//cout << array.at(i) << " ";
cout << "\nValues counted: " << numValues;
}
myFile.close();
mergeSort(array, numInversion);
cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";
for (int i = 0; i < 100000; i++)
cout << array[i] << "\n";
}
void mergeSort(vector<int> &array, int &inversionCount)
{
if (array.size() <= 1) return;
int middle = array.size() / 2;
vector<int> left;
vector<int> right;
for (int i = 0; i < middle; i++)
{
left.push_back(array[i]);
inversionCount++;
}
for (int j = 0; j < (array.size() - middle); j++)
{
right.push_back(array[middle + j]);
inversionCount++;
}
mergeSort(left,inversionCount);
mergeSort(right,inversionCount);
merge(left, right, array, inversionCount);
}
void merge(vector<int> &left, vector<int> &right, vector<int> &array, int &inversionCount)
{
int leftSize = left.size();
int rightSize = right.size();
int i = 0, l = 0, r = 0;
while (l < leftSize && r < rightSize)
{
if (left[l] < right[r])
{
array[i] = left[l];
i++;
l++;
}
else
{
array[i] = right[r];
i++;
r++;
}
}
while (l < leftSize)
{
array[i] = left[l];
i++;
l++;
}
while (r < rightSize)
{
array[i] = right[r];
i++;
r++;
}
}
从您的评论来看,您似乎走在正确的道路上。
但是,让我们看一些随机数的情况,并跳过前几次合并。我们将采用 [4,5,7,8,9] 和 [1,2,3,5,6] 的情况。也许已经计算了一些反转,但我们只是从这里开始。
首先,我们检查[4]是否大于[1]。确实如此,所以我们必须增加反转计数器。然而,在这种情况下,[4] 也大于 [2] 和 [3],这也必须进行检查。
问题是,我们怎样才能做到这一点?好吧,当我们意识到 [4] 大于 [1] 时,我们可以在右侧数组内启动另一个循环,增加反转计数器,直到遇到大于或等于 4 的值,然后停止。因此,在本例中,我们对 [4] 对 [1]、[2] 和 [3] 进行+1,然后在右侧停止[5]。这样我们就剩下+3,然后我们在新数组中放入 4,并从 left[5] 开始,再次向上计数。
显然,在开始检查之前我们必须保存 right[1] 的索引,否则 MergeSort 算法可能会搞砸。
这是一种幼稚的方法,因为当我们查看 left[5] 时,实际上没有理由一路倒数,因为我们知道 left[5] > left[4],并且我们已经知道 left [4] 大于 right[] 数组中的几个值。对于 100,000 个值之类的值,这种天真可能会导致您的程序速度明显减慢。