理解合并排序代码

Question

我正在尝试使用以下网站作为资源来实现合并排序。

http://interactivepython.org/courselib/static/pythonds/SortSearch/TheMergeSort.html

https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/p/challenge-implement-merge

在我看来，我的代码看起来很好；但是，考虑到我的不正确输出，它显然是错误的。我不知道它在哪里，为什么不对。当我看到它的图像解释时，我想我理解合并排序，但是试图实现它是非常困难的。我试图给所有变量命名一些意义，以帮助减少混淆("i“、"j”、"k“、"m”和"n“都很难跟踪它们所代表的内容)。我也尝试过使用print语句来帮助调试代码，但是递归对我来说从来都不容易，所以我不知道我的print语句到底告诉我什么--除了输出是错误的。我也尝试过使用调试器，但是由于任何原因，调试器没有列出我的数组中的值，所以我无法通过调试器进行实际操作。任何帮助澄清合并排序的实现将是非常感谢的。

#include <stdio.h>

void merge_sort(int array[], int startIndex, int endIndex);
void merge(int array[], int startIndex, int midIndex, int endIndex);

int main(void)
{
    int size = 8;
    int numbers[8] = {14, 7, 3, 12, 9, 11, 6, 2};
    
    printf("Unsorted Array!\n");
    for(int i = 0; i < size; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
    
    merge_sort(numbers, 0, 7);
    
    printf("Sorted Array!\n");
    for(int i = 0; i < size; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
}

void merge_sort(int array[], int startIndex, int endIndex)
{
    // determine size of the array
    int size = (endIndex - startIndex) + 1; // updated
    
    // if the array has more than 1 element then it needs broken down into smaller arrays
    if(size > 1)
    {
        int midIndex = (startIndex + endIndex) / 2;
        
        merge_sort(array, startIndex, midIndex); // Sort the LEFT side
        merge_sort(array, midIndex + 1, endIndex); // Sort the RIGHT side
        
        merge(array, startIndex, midIndex, endIndex);
    }
}

void merge(int array[], int startIndex, int midIndex, int endIndex)
{
   int leftSize = midIndex - startIndex + 1;
   int rightSize = endIndex - midIndex;
   int originalArrayIndex = 0;
   int leftArray[leftSize];
   int rightArray[rightSize];
   int currentLeftIndex = 0;
   int currentRightIndex = 0;
   
   // fill the leftArray
   for(int i = 0; i < leftSize; i++)
   {
       leftArray[i] = array[i];
       printf("%i ", leftArray[i]);
   }
   printf(" === Left array\n");
   
   // fill the rightArray
   for(int i = 0; i < rightSize; i++)
   {
       rightArray[i] = array[leftSize + i];
       printf("%i ", rightArray[i]);
   }
   printf(" === Right array\n");
   
   // do the actual merge
   // leftStart < leftSize and rightStart < rightSize
   while((currentLeftIndex < leftSize) && (currentRightIndex < rightSize))
   {
       // if the left array value is smaller than the right array value then that means the left array value goes into the original array[]
       if(leftArray[currentLeftIndex] < rightArray[currentRightIndex])
       {
           array[originalArrayIndex] = leftArray[currentLeftIndex];
           originalArrayIndex++;
           currentLeftIndex++;
       }
       else
       {
           array[originalArrayIndex] = rightArray[currentRightIndex];
           originalArrayIndex++;
           currentRightIndex++;
       }
   }
   
   // no clue what this is
   while(currentLeftIndex < leftSize)
   {
       array[originalArrayIndex] = leftArray[currentLeftIndex];
       originalArrayIndex++;
       currentLeftIndex++;
   }
   
   // no clue what this is
   while(currentRightIndex < rightSize)
   {
       array[originalArrayIndex] = rightArray[currentRightIndex];
       originalArrayIndex++;
       currentRightIndex++;
   }
   
   for(int i = 0; i < leftSize; i++)
   {
       printf("%i ", leftArray[i]);
   }
   printf(" ==== left array after sort\n");
   
   for(int i = 0; i < rightSize; i++)
   {
       printf("%i ", rightArray[i]);
   }
   printf(" ==== right array after sort\n");
   
   for(int i = 0; i < endIndex + 1; i++)
   {
       printf("%i ", array[i]);
   }
   printf(" ===== post merge =====\n");
}

产出列示如下：

未排序阵列！ 14 7 3 12 9 11 6 14 7 ===左数组 3 12 ===右数组 排序后的14 7 ====左数组 排序后的3 12 ====右数组 3 12 14 7 =====合并后===== 3 12 ===左数组 14 7 ===右数组 排序后的3 12 ====左数组 排序后的147 ====右数组 3 12 14 7 11 6 =====合并后===== 3 12 14 7 ===左数组 9 11 6 2 ===右数组 排序后的3 12 14 7 ====左数组 排序后的9 11 6 2 ====右数组 3 9 11 6 2 12 14 7 =====合并后===== 排序阵列！ 9 11 6 2 12 14 7

最新产出：

未排序阵列！ 14 7 3 12 9 11 6 14 ===左数组 7 ===右阵列 7 14 =====合并后===== 7 ===左数组 14 ===右数组 7 14 3 12 =====合并后===== 7 14 ===左数组 3 12 ===右数组 3 7 12 14 =====合并后===== 3 ===左数组 7 ===右阵列 3 7 12 14 9 =====合并后===== 3 ===左数组 7 ===右阵列 3 7 12 14 11 6 =====合并后===== 3 7 ===左数组 12 14 ===右阵 3 7 12 14 11 6 =====合并后===== 3 7 12 14 ===左数组 9 11 6 2 ===右数组 合并后===== ===== 3 7 9 11 6 2 12 14 排序阵列！ 3 7 9 11 6 2 12 14

Answer 1

这个版本有效。它是原始代码，在注释中注意到//修复了这一行//。其他更改是由于使用Microsoft编译器(旧C语法)造成的。也清理了压痕。

#include <stdio.h>

void merge_sort(int array[], int startIndex, int endIndex);
void merge(int array[], int startIndex, int midIndex, int endIndex);

int main(void)
{
int i;            // my compiler is old style c
int size = 8;
int numbers[8] = {14, 7, 3, 12, 9, 11, 6, 2};

    printf("Unsorted Array!\n");
    for(i = 0; i < size; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");

    merge_sort(numbers, 0, 7);

    printf("Sorted Array!\n");
    for(i = 0; i < size; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
    return 0;       // added this //
}

void merge_sort(int array[], int startIndex, int endIndex)
{
// determine size of the array
int size = (endIndex - startIndex) + 1; // updated
int midIndex;    // my compiler is old style C compiler

// if the array has more than 1 element then it needs broken down into smaller arrays
    if(size > 1)
    {
        midIndex = (startIndex + endIndex) / 2;
        merge_sort(array, startIndex, midIndex); // Sort the LEFT side
        merge_sort(array, midIndex + 1, endIndex); // Sort the RIGHT side
        merge(array, startIndex, midIndex, endIndex);
    }
}

void merge(int array[], int startIndex, int midIndex, int endIndex)
{
int leftSize = midIndex - startIndex + 1;
int rightSize = endIndex - midIndex;
int originalArrayIndex = startIndex;   // fixed this line //
//  my compiler doesn't support variable length arrays
//  so allocating from the stack (neither works on large arrays)
int *leftArray  = _alloca(leftSize*sizeof(int));
int *rightArray = _alloca(rightSize*sizeof(int));
// int leftArray[leftSize];
// int rightArray[rightSize];
int currentLeftIndex = 0;
int currentRightIndex = 0;
int i;    // my compiler is old style c compiler

    // fill the leftArray
    for(i = 0; i < leftSize; i++)
    {
        leftArray[i] = array[startIndex+i];   // fixed this line //
        printf("%i ", leftArray[i]);
    }
    printf(" === Left array\n");

    // fill the rightArray
    for(i = 0; i < rightSize; i++)
    {
        rightArray[i] = array[midIndex + 1 + i];  // fixed this line //
        printf("%i ", rightArray[i]);
    }
    printf(" === Right array\n");

    // do the actual merge
    // leftStart < leftSize and rightStart < rightSize
    while((currentLeftIndex < leftSize) && (currentRightIndex < rightSize))
    {
        // if the left array value is smaller than the right array value then that means the left array value goes into the original array[]
        if(leftArray[currentLeftIndex] < rightArray[currentRightIndex])
        {
            array[originalArrayIndex] = leftArray[currentLeftIndex];
            originalArrayIndex++;
            currentLeftIndex++;
        }
        else
        {
            array[originalArrayIndex] = rightArray[currentRightIndex];
            originalArrayIndex++;
            currentRightIndex++;
        }
    }

    // copy any data remaining in leftArray
    while(currentLeftIndex < leftSize)
    {
        array[originalArrayIndex] = leftArray[currentLeftIndex];
        originalArrayIndex++;
        currentLeftIndex++;
    }

    // copy any data remaining in rightArray
    while(currentRightIndex < rightSize)
    {
        array[originalArrayIndex] = rightArray[currentRightIndex];
        originalArrayIndex++;
        currentRightIndex++;
    }

    for(i = 0; i < leftSize; i++)
    {
        printf("%i ", leftArray[i]);
    }
    printf(" ==== left array after sort\n");

    for(i = 0; i < rightSize; i++)
    {
        printf("%i ", rightArray[i]);
    }
    printf(" ==== right array after sort\n");

    for(i = startIndex; i < endIndex + 1; i++)   // fix
    {
        printf("%i ", array[i]);
    }
    printf(" ===== post merge =====\n");
}

Answer 2

您的错误在于：

   // fill the rightArray
   for(int i = 0; i < rightSize; i++)
   {
       rightArray[i] = array[rightSize + i];
       printf("%i ", rightArray[i]);
   }
   printf(" === Right array\n");

您需要缩进左数组大小

   rightArray[i] = array[leftSize + i];

顺便说一句，你评论的部分

//不知道这是什么

在程序已经完成插入两个数组之一的所有索引的情况下，是否继续插入索引。

更新:还有另一个(更大的)问题。您还需要跟踪原始数组中的当前位置。如果仔细观察，您会发现，即使在使用numbers[0]的右半部分时，也始终会复制从它开始的值。但是，保留另一个计数器是一种很麻烦的方法，因此请考虑将函数定义更改为：

merge_sort (int array[], int arraySize);
merge (int leftArray[], int leftSize, int rightArray[], int rightSize, int targetArray[]);

这将有助于保持清洁和简单。它应该是这样的：

#include <stdio.h>

void merge_sort(int array[], int arraySize);
void merge(int leftArray[], int leftSize, int rightArray[], int rightSize, int targetArray[]);

int main(void)
{
    int numbers[8] = { 14, 7, 3, 12, 9, 11, 6, 2 };
    int size = sizeof(numbers) / sizeof(int);

    printf("Unsorted Array!\n");
    for (int i = 0; i < size; i++)
    {
        printf("%i, ", numbers[i]);
    }
    printf("\n");

    merge_sort(numbers, size);

    printf("Sorted Array!\n");
    for (int i = 0; i < size; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
}

void merge_sort(int array[], int arraySize)
{
    if (arraySize > 1)
    {
        int leftSize = arraySize / 2;
        int rightSize = arraySize - leftSize;

        merge_sort(array, leftSize); // Sort the LEFT side
        merge_sort(array + leftSize, rightSize); // Sort the RIGHT side

        int* targetArray = (int*)malloc(arraySize * sizeof(int));
        merge(array, leftSize, array + leftSize, rightSize, targetArray);
        memcpy(array, targetArray, arraySize * sizeof(int));

        free(targetArray);
    }
}

void merge(int leftArray[], int leftSize, int rightArray[], int rightSize, int targetArray[])
{
    int currentLeftIndex = 0;
    int currentRightIndex = 0;
    int targetIndex = 0;

    while ((currentLeftIndex < leftSize) && (currentRightIndex < rightSize))
    {
        if (leftArray[currentLeftIndex] < rightArray[currentRightIndex])
        {
            targetArray[targetIndex] = leftArray[currentLeftIndex];
            currentLeftIndex++;
        }
        else
        {
            targetArray[targetIndex] = rightArray[currentRightIndex];
            currentRightIndex++;
        }
        targetIndex++;
    }

    while (currentLeftIndex < leftSize)
    {
        targetArray[targetIndex] = leftArray[currentLeftIndex];
        targetIndex++;
        currentLeftIndex++;
    }

    while (currentRightIndex < rightSize)
    {
        targetArray[targetIndex] = rightArray[currentRightIndex];
        targetIndex++;
        currentRightIndex++;
    }
}

Answer 3

在merge中初始化临时左、右数组时，需要修复要访问的索引。例如，您目前有

// fill the leftArray
for(int i = 0; i < leftSize; i++)
{
    leftArray[i] = array[i];
    printf("%i ", leftArray[i]);
}
printf(" === Left array\n");

// fill the rightArray
for(int i = 0; i < rightSize; i++)
{
    rightArray[i] = array[rightSize + i];
    printf("%i ", rightArray[i]);
}
printf(" === Right array\n");

但这假设array是原始数组的一部分。尽管从视觉上看，合并算法实际上将原始数组拆分为子数组，但代码实际上并没有这样做。您仍然在修改原始数组，但是参数int startIndex, int midIndex, int endIndex就像原始数组中的边框一样。因此，在初始化leftArray和rightArray时，需要使用如下参数访问array的元素，

// fill the leftArray
for(int i = 0; i < leftSize; i++)
{
    leftArray[i] = array[i];
    printf("%i ", leftArray[startIndex + i]);
}
printf(" === Left array\n");

// fill the rightArray
for(int i = 0; i < rightSize; i++)
{
    rightArray[i] = array[midIndex + i];
    printf("%i ", rightArray[i]);
}
printf(" === Right array\n");