c - 合并排序不起作用

Question

我花了几个小时试图找出这段代码的问题所在，我在谷歌上搜索到的所有归并排序算法看起来几乎都是一样的，这个不起作用； 尝试对指针数组进行合并排序:

输出: 2| 2| 3| 3| 4| 5| 4| 4| 7| 7|

#include <stdlib.h>
#include <stdio.h>
void merge( int ** pointerArray, int pivot,int size){
int leftSize=pivot;
int rightSize=size;
 int leftIndex=0, rightIndex=pivot, newIndex=0;

int **tempArray= (int **)malloc(sizeof(int *)*size);

while (leftIndex < leftSize && rightIndex < rightSize) {//merging two sorted array

    if ((*pointerArray)[leftIndex]<=(*pointerArray)[rightIndex] )
        (tempArray)[newIndex++]=(pointerArray)[leftIndex++];
    else
        (tempArray)[newIndex++]=(pointerArray)[rightIndex++];



}

while (leftIndex<leftSize )//rest of left array
    (tempArray)[newIndex++]=(pointerArray)[leftIndex++];

while (rightIndex<rightSize)//rest of right array
    (tempArray)[newIndex++]=(pointerArray)[rightIndex++];


    for (int i=0; i<size; i++)//copying the tempArray to the original array
    pointerArray[i]=tempArray[i];


free(tempArray);

}
void mergeSort( int ** ptrarray, int size){
if (size==1)
    return;
int pivot=size/2;
mergeSort(ptrarray, pivot);
mergeSort(ptrarray+pivot, size-pivot);
merge(ptrarray, pivot, size);



}

int** pointerSort(int* arr, unsigned int size,
              char ascend_flag)
{
int **pointerArray= (int **)malloc(sizeof(int *)*size);

for (int i=0; i<size; i++)
    pointerArray[i]=&arr[i];

mergeSort(pointerArray, size);

return pointerArray;
}

int  main()
{
int size=10;
int array[10]={3,2,3,5,4,7,2,7,4,4};
char ascend_flag =1;
int ** pointer= pointerSort(array, size, ascend_flag);

for (int **p=pointer; p-pointer<size; p++)//print sorted array
    printf(" %d|", *(*p));


}

Answer 1

虽然不清楚为什么要对指向整数的指针数组进行排序，而不是仅仅复制整数本身，但这肯定会让你误入歧途。当你说:

if ((*pointerArray)[leftIndex] <= (*pointerArray)[rightIndex])

您没有比较您想要的内容。

*pointerArray 与 pointerArray[0] 或列表中第一个 int * 相同。您正在将 pointerArray[0][leftIndex] 与 pointerArray[0][rightIndex] 进行比较，而您想要的实际上是 pointerArray[leftIndex][0] 和 pointerArray[rightIndex][0]，如下所示:

if (*(pointerArray[leftIndex]) <= *(pointerArray[rightIndex]))

工作示例:https://ideone.com/Kgl3oO

p.s. 事实上，数组在您的版本中似乎已排序，这是一个令人愉快的意外。尝试使用更混合的初始数组，例如:

int array[10] = {97, 4, 2, 107, 6, 7, 14, 22, 89, 6};

你会看到类似的结果

4| 97| 7| 14| 22| 6| 2| 6| 107| 89|