Mergesort不起作用

Question

一直在嘗試幾個小時才能找到這段代碼出了什麼問題，並且所有mergesort的算法我一直在使用，看起來幾乎相同，這個不起作用; 試圖對指針數組進行mergesort：

輸出： 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

雖然目前還不清楚爲什麼要對指針進行排序而不是僅僅複製整個ints，它肯定會讓您誤入歧途。當你說：

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

附：陣列在您的版本中出現種類排序的事實是一個令人高興的事故。以更加混亂的初始陣列試試吧，比如：

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

，你會看到類似的結果

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