6

我正在尝试实现合并排序，但不知何故已经卡了一天。

[抱歉粘贴了大量代码，但没有它就无法做到]

执行：

合并排序 - 函数

int mergeSort(int arr[], int low, int high)
{
        int half = (low + high) / 2 ;    /* FInd the middle element */ 
        if (low < high)
        {
            if (high - low == 1)             /* If only one element, return */
                return;
            mergeSort(arr,low,half);    /* Sort First Half */
            mergeSort(arr,half, high); /* Sort Second Half */
            merge(arr,low,half,high);  /* Merge */
        }
      return SUCCESS;
}

合并步骤 - 合并函数

int merge(int arr[], int low, int half, int high)
{
    int i = 0, j =0, k = 0, l = 0, temp;    /* Initialize indices */

    for(i = low, j = half;i < half && j < high; i++,j++)    /* Swap in the array itself if the elements are out of order */
    {
        if (arr[i] > arr[j])
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

    }

    i = 0,j = low;  /* Compare and copy the elements in a global arrray C */
    for(k = 0; k < SIZE && i < low && j < high; k++)
    {
        if (arr[i] < arr[j])
        {
            c[k] = arr[i];
            i++;
        }
        else
        {
            c[k] = arr[j];
            j++;
        }
    }

    if (i < j) /* Copy remaining elements to the end of the array C */
    {
        for (l = i; l < low; l++)
        {
            c[k++] = arr[l];
        }
    }
    else
    {
        for (l = j; l < high; l++)
        {
            c[k++] = arr[l];
        }
    }

输出

8 --> 9 --> 
4 --> 5 --> 8 --> 9 --> 
4 --> 5 --> 8 --> 9 --> 
1 --> 2 --> 4 --> 5 --> 8 --> 9 --> /* Sorting when left is sorted but right is in the process ? */
4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 1 --> 2 --> 
1 --> 2 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 
1 --> 2 --> 6 --> 7 --> 4 --> 5 --> 8 --> 9 -->

问题描述

我没有使用任何本地数组来存储数组的元素。相反，如果元素乱序，则交换元素，然后通过比较将其复制到全局数组中示例：如果我有数组

{ 9, 8, 4, 5, 2, 1, 7, 6}

然后，首先{8,9}将被排序，然后{4,5}将被排序，然后在复制过程时{8,4}将进行比较，依此类推。发生以下递归调用

mergeSort(0,8) -> mergeSort(0,4) , mergeSort(4,8), merge(0,4,8)
mergeSort(0,4) -> mergeSort(0,2) , mergeSort(2,4), merge(0,2,4)
mergeSort(0,2) -> 1 element calls
and so on.

当{4,5,8,9}排序时调用合并，调用右边时merge(4,5,6)我有以下数组

{4,5,8,9,1,2,7,6}

所以，算法试图排序{4,5,8,9}，{1,2}什么时候{1,2}不是这个子问题的一部分，即我想要{1,2}并'{6,7}成为{1,2,6,7}然后将这两者结合起来。

我该如何克服呢？我被困了这么多小时。

非常感谢

4

0 回答 0