这段归并排序,用C写完为什么是部分排序的? 财富值65

2016-10-07 14:36发布

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
", array[i]);     }      return 0; } 

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

1条回答
Scar - 淄博seo孔祥永博客
1楼 · 2016-10-07 14:25.采纳回答

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

一周热门 更多>