坦白说,我是一名学生,在合并排序方面遇到了麻烦。目的显然是要有一个 O(n log n),但它更多的是 n^2。我认为问题出在 tempList 中,正如您将在代码中看到的那样,但在程序描述中它说要使用 static int tempList[LIST_SIZE] 来避免降级。
这是我所拥有的,使用 start 的运行时约为 16000,这显然是合并排序的一种方式。
void mergeSort(int randomNum[], int lowIdx, int highIdx)
{
int midIdx;
if (lowIdx < highIdx)
{
midIdx = (highIdx + lowIdx) / 2;
mergeSort(randomNum, lowIdx, midIdx);
mergeSort(randomNum, midIdx + 1, highIdx);
merge(randomNum, lowIdx, midIdx, highIdx);
}
}
这是排序的第二部分
void merge(int randomNum[], int lowIdx, int midIdx, int highIdx)
{
static int tempList[MAX_SORT];
for (int count = 0; count <= highIdx; count++)
tempList[count] = randomNum[count];
int leftIdx = lowIdx,
rightIdx = midIdx + 1,
tempPos = lowIdx;
while (leftIdx <= midIdx && (rightIdx <= highIdx))
{
if (tempList[leftIdx] <= tempList[rightIdx])
{
randomNum[tempPos] = tempList[leftIdx];
leftIdx++;
}
else
{
randomNum[tempPos] = tempList[rightIdx];
rightIdx++;
}
tempPos++;
}
while (leftIdx <= midIdx)
{
randomNum[tempPos] = tempList[leftIdx];
tempPos++;
leftIdx++;
}
while (rightIdx <= highIdx)
{
randomNum[tempPos] = tempList[rightIdx];
tempPos++;
rightIdx++;
}
}
程序的细节是我们有一个包含 100000 个随机数的数组,并使用各种排序算法对其进行排序。其他类型按预期工作,但与 big-O 的预期相比,这个似乎有很大差距。
有人可以帮忙吗?
最佳答案
不确定这是否是您的全部问题,但这是一个问题:
您正在将 randomNum
复制到 tempList
,从 0
到 highIdx
,但您只能访问 tempList
从 lowIdx
到 highIdx
。
这意味着您从 0
复制到 lowIdx
的所有项目都是浪费的拷贝。
解决方案:只复制你需要的。
for (int count = lowIdx; count <= highIdx; count++)
关于c++ - 无法将合并排序设为 O(n log n),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26154721/