c++ - 这段归并排序，用C写完为什么是部分排序的？

问题描述

问 题

1.用C语言写了一段归并排序，是按照邓俊辉博士的数据结构来的。
但是没有判断是那部分程序出错了，结果老是部分排序的

void mergeSort(int *array, int lPos, int rPos)
{
    int miPos;
    
    if (rPos - lPos >= 2)
    {
        miPos = (rPos + lPos) >> 1;
        mergeSort(array, lPos, miPos);
        mergeSort(array, miPos, rPos);
        merge(array, lPos, miPos, rPos);
    }
}

void merge(int *array, int lPos, int miPos, int rPos)
{
    int leftLen, rightLen, *lArray, *rArray;

    //将数组左侧的部分复制出来
    leftLen = miPos - lPos;
    
    //为左侧部分开辟一块内存空间
    lArray = MALLOC(leftLen, int);
    for(int i = 0; i < leftLen; i++)
    {
        lArray[i] = array[i];
    }
    
    //让rArray指向右侧部分的开始端点
    rightLen = rPos - miPos;
    rArray = &array[miPos];

    for(int i = 0, j = 0, k = 0; j < leftLen; )
    {
        if(k < rightLen && (rArray[k] < lArray[j]))
        {
            array[i++] = rArray[k++];
        }
        if(rightLen <= k || (lArray[j] <= rArray[k]))
        {
            array[i++] = lArray[j++];
        }
    }
    free(lArray);
}

//以下部分是main函数的部分
int main(void)
{
    int array[10] = {0, 1, 8, 5, 6, 7, 2, 9, 3, 4};

    mergeSort(array, 0, 10);
    
    for(int i = 0; i < 10; ++i)
    {
        printf ("%d\n", array[i]);
    }

    return 0;
}

2.我猜测是分治的时候，数组元素出现了覆盖，或者漏掉了某些元素，所以导致排序失败？
所以错误应该是在mergeSort中。
3.而merge函数的for循环中，逻辑判断是两个情况，第一左端元素小于右端元素，第二种是左端元素大于右端元素。

解决方案

啊，已经解决了。因为array的指针位置不对。每次操作的都是第一个元素。

这篇关于c++ - 这段归并排序，用C写完为什么是部分排序的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！