问题描述
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 ('%dn', array[i]); } return 0;}
2.我猜测是分治的时候，数组元素出现了覆盖，或者漏掉了某些元素，所以导致排序失败？所以错误应该是在mergeSort中。3.而merge函数的for循环中，逻辑判断是两个情况，第一左端元素小于右端元素，第二种是左端元素大于右端元素。
问题解答
回答1：啊，已经解决了。因为array的指针位置不对。每次操作的都是第一个元素。
