需要使用数组指针、其长度和合并函数的工作区数组在C中实现递归合并排序代码

Question

我需要为最多100000个整数的数组实现mergesort，但规范有点麻烦：我需要使用一个指向整数数组的指针、它的长度和一个用于合并的额外工作区数组

mergesort函数应该如下所示：

void merge_sort(int *a, int *w, int n)

其中a是要排序的，w是用于合并的工作空间，不能在我想要排序的之间使用数组和两个索引

伪代码：

merge_sort(int *a, int *w, int n) {
/* take care of stopping condition first */
if the array to be sorted has fewer than two elements then
return
merge_sort( first half of array a);
merge_sort( second half of array a);
merge the two halves of array a into array w
copy array w back into array a
}

merge(int *array, int *workspace, int len) {
initialise indices to point to the beginning of
the left and right halves of array
while there are elements in both halves of array {
compare the elements at the current left and right indices
put the smallest into workspace and increment both the index
it was taken from, and the index in workspace
}
add any remaining elements from left half of array to workspace
add any remaining elements from right half of array to workspace
}

到目前为止，我得到的是：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_MAX 100000
void merge_sort(int *a, int *w, int n) {
if (n == 1)
return;
else {
int *temp;
merge_sort(a, w, n / 2);
merge_sort(a + (n / 2), w, (n - (n / 2)));
/** Cannot figure what to pass to merge since it has to be the two halves          
and how to copy contents of a to w **/
} 
}
void merge(int *a, int *w, int n) {
/** Cannot figure this out **/
}
int main(void) {
int my_array[ARRAY_MAX];
int work_space[ARRAY_MAX];
int count = 0;
int i;
while (count < ARRAY_MAX && 1 == scanf("%d", &my_array[count])) {
count += 1;
}
start = clock();
merge_sort(my_array, workspace, count);
end = clock();
merge_sort(my_array, work_space, count);
for (i = 0; i < count; i++) {
printf("%dn", my_array[i]);
}
fprintf(stderr, "%d %f n", count, (end - start) / (double)CLOCKS_PER_SEC);
return EXIT_SUCCESS;
}

Answer 1

函数merge_sort中的合并阶段并行地在的两半上迭代，每次从两侧取最小元素：

void merge_sort(int *a, int *w, int n) {
if (n < 2) {
return;
} else {
int i, j, k;
int n1 = n / 2;
int *b = a + n1;
int n2 = n - n1;
/* sort the left half */
merge_sort(a, w, n1);
/* sort the right half */
merge_sort(b, w, n2);
/* merge the halves into w */
for (i = j = k = 0; i < n1 && j < n2;) {
if (a[i] <= b[j]) {
/* get smallest value from a */
w[k++] = a[i++];
} else {
/* get smallest value from b */
w[k++] = b[j++];
}
}
/* copy remaining elements from a */
while (i < n1) {
w[k++] = a[i++];
}
/* copy remaining elements from b */
while (j < n2) {
w[k++] = b[j++];
}
/* copy sorted elements back to a */
for (i = 0; i < n; i++) {
a[i] = w[i];
}
} 
}

代码的其余部分也有一些问题：

• 2个100000 int的数组可能会超出自动变量的可用空间
• 对数组进行两次排序
• 未定义start和end

这是一个更正的版本：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_MAX 100000
int main(void) {
int my_array[ARRAY_MAX];
int work_space[ARRAY_MAX];
int i, count;
clock_t start, end;
count = 0;
while (count < ARRAY_MAX && scanf("%d", &my_array[count]) == 1) {
count += 1;
}
start = clock();
merge_sort(my_array, workspace, count);
end = clock();
for (i = 0; i < count; i++) {
printf("%dn", my_array[i]);
}
fprintf(stderr,"%d %fn", count, (end - start) / (double)CLOCKS_PER_SEC);
return EXIT_SUCCESS;
}

Answer 2

请记住，在C中，当您将数组作为参数发送到函数时，实际发送的是指向第一个元素的指针。然后，您可以在函数中使用该指针，其方式与数组非常相似。所以，如果你对(我想(你的家庭作业描述中的"指针"感到困惑，也许这就是原因？