对于一个赋值,我们要用 C 语言编写归并排序函数:
sort(int* array, unsigned len);
我已经编写并运行了代码,但它的运行时间是 O(N^2*log[N])
,这违背了归并排序的目的。效率低下的原因是因为合并部分如下:
while(ct1 < len1 && ct2 < len2){
if(array[0] < array[len1 - ct1]){
ct1++;
array++; // no longer look at that element
}
else{
int position = len1 - ct1;
int hold = array[position];
while(position > 0){
array[position] = array[position - 1];
position--;
}
array[0] = hold;
ct2++;
array++;
}
}
其中 ct1
是左列表的计数器,ct2
是右列表的计数器,array 是指向数组的指针。 ct1
和 ct2
初始设置为零。就像我说的,这行得通,只是效率低下,因为你必须改变一切。我想在排序之前将子数组拆分为两个临时数组,但你不能创建长度未定义为常量的数组。我还应该注意,虽然我可以使用辅助函数,但我不能更改函数参数:必须有一个指向数组的指针和长度。
最佳答案
您可以创建长度不固定的数组,google malloc
。合并排序需要使用辅助内存才能正常工作。完成后,您必须释放
malloc
分配的内存。
关于c - 合并排序在 C 与 O(N*log[N]) 运行时,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5657620/