c - 指针数组上的合并排序实现

Question

我收到大学的作业，要编写一个程序，该程序接收整数数组及其大小，并返回指向原始数组值的已排序指针数组。排序必须通过使用 mergeSort 算法来完成，并且不允许我触摸原始数组，只能更改指针数组。

谁能帮帮我吗？这是我的代码:

void sortedPointerArray (int **arr1[], int size1, int **arr2[], int size2, int **arr3[])
{
    int read1, read2, writeind;

    read1 = read2 = writeind = 0;
    while( (read1<size1) && (read2 < size2))
    {
            if (*(arr1[read1]) < *(arr2[read2]))
            {
                    arr3[writeind] = arr1[read1];
                    writeind++;
                    read1++;
            }
            else
            {
                    arr3[writeind] = arr2[read2];
                    writeind++;
                    read2++;
            }

    }
    while (read1 < size1)
    {
            arr3[writeind] = arr1[read1];
            writeind++;
            read1++;
    }
    while (read2 < size2)
    {
            arr3[writeind] = arr2[read2];
            writeind++;
            read2++;
    }
}

void mergeSort (int **arr, int size)
{
    int temp, i;

    if(size <=1)
            return;
    else
    {
            mergeSort(arr, size/2);
            mergeSort(arr+(size/2), size-(size/2));
            int** temp = (int **)malloc(size*sizeof(int *));
            sortedPointerArray(arr,size/2,arr+(size/2),size-(size/2),temp);
            for (i=0; i<size; i++)
                    (*arr)[i] = (*temp)[i];
            free(temp);
    }
}

由于某种未知的原因，我无法编译它并且它不起作用......任何帮助将不胜感激!

Answer 1

#include <stdlib.h>
#include <stdio.h>

void mergeSort (int **arr, size_t size);
void sortedPointerArray (int **arr1, size_t size1, int **arr2, size_t size2, int **arr3);

void sortedPointerArray (int **arr1, size_t size1, int **arr2, size_t size2, int **arr3)
{
    size_t read1, read2, writeind;

    for(read1=read2=writeind=0; read1 < size1 && read2 < size2; )
            arr3[writeind++] = (*arr1[read1] < *arr2[read2])
                   ? arr1[read1++]
                   : arr2[read2++]
                   ;

    while (read1 < size1)
            arr3[writeind++] = arr1[read1++];

    while (read2 < size2)
            arr3[writeind++] = arr2[read2++];
}

void mergeSort (int **arr, size_t size)
{
    size_t idx;
    int **temp ;

    if(size < 2) return;

    mergeSort(arr, size/2);
    mergeSort(arr+(size/2), size-(size/2));

    temp = malloc(size*sizeof *temp);
    sortedPointerArray(arr,size/2,arr+(size/2),size-(size/2),temp);
    for (idx=0; idx<size; idx++)
            arr[idx] = temp[idx];
    free(temp);
}


#define COUNTOF(a) (sizeof a/ sizeof a[0])
int array[] = { 3,2,4,5,9,8,7,1,6,0};

int *ptrs[COUNTOF( array)];

int main(void)
{
unsigned idx;

for(idx=0; idx < COUNTOF( array); idx++ ) ptrs[idx] = array+idx;

mergeSort(ptrs, COUNTOF(ptrs) );

for(idx=0; idx < COUNTOF(ptrs); idx++ ) {
        printf("%u: %p %d\n", idx, (void*) ptrs[idx], *ptrs[idx] );
        }
return 0;
}

输出:

0: 0x601064 0
1: 0x60105c 1
2: 0x601044 2
3: 0x601040 3
4: 0x601048 4
5: 0x60104c 5
6: 0x601060 6
7: 0x601058 7
8: 0x601054 8
9: 0x601050 9

评论/更改:

• 删除了令人困惑(且错误)的额外间接级别
• 删除了多余的括号
• 删除了不必要的 malloc 转换
• 压缩了合并循环以使用dst[aaa++] = src[bbb++];
• 将所有索引更改为无符号 (size_t) 类型。
• 删除了 if (size <2) return; 之后的 else 部分
• 添加了驱动程序。
• 去掉了大括号并引入了三元运算符，让老师感到沮丧