这是一个创建于 3930 天前的主题，其中的信息可能已经有所发展或是发生改变。
#include <stdio.h> #include <stdlib.h> typedef int T; void merge(T _elem[], int lo, int mi, int hi) { // lb, lc 作为待排序数组左右两块的边界哨兵 int lb = mi - lo, lc = hi - mi; // 开辟一个临时的空间用于存储前半段待排序数组 T* B = (T* )malloc(sizeof(T)*lb); // 将前半段待排序数组复制到临时空间 B 中 for (int i = 0; i < lb; i++) B[i] = _elem[i]; // 待排序数组的后半段为 C T* C = _elem + mi; // B[j]和C[k]中的小者续至A末尾 for (int i = 0, j = 0, k = 0; j < lb || k < lc;) { if (j < lb && (lc <= k || B[j] <= C[k])) _elem[i++] = B[j++]; if (k < lc && (lb <= j || C[k] < B[j])) _elem[i++] = C[k++]; } free(B); } void mergeSort(T _elem[], int lo, int hi) { if (hi - lo < 2) return; int mi = (lo + hi) >> 1; mergeSort(_elem, lo, mi); mergeSort(_elem, mi, hi); merge(_elem, lo, mi, hi); } int main() { T elem[19] = {53, 130, 120, 14, 206, 31, 380, 39, 402, 146, 491, 51, 54, 59, 722, 79, 82, 186, 92}; mergeSort(elem, 0, 19); for (int i = 0; i < 19; i++) printf("%d\t", elem[i]); return 0; }  | 1 diamrem 2015 年 4 月 9 日  1 for (int i = 0; i < lb; i++) B[i] = _elem[i]; 每次都从_elme的第一个元素开始复制到临时数组里面？这里应该是_elem[lo +i]之类的吧 后面没看。 找个小input用gdb或者lldb之类的调调吧…… |
 | 2 SPACELAN 2015 年 4 月 9 日 1. mergeSort(elem, 0, 19) >> mergeSort(elem, 0, 18)， 第三个参数表示下标，不是长度。 2. mergeSort(_elem, mi, hi) >> mergeSort(_elem, mi + 1, hi)，子序列不要有重叠。 |
4 zeroday OP @SPACELAN 好像不是这个问题，这里第三个参数，我作为哨兵，并且取不到这个下标。所以这个样看来 mergeSort(elem, 0, 19) mergeSort(_elem, mi, hi) 就没错了。 因为在 mergeSort(_elem, lo, mi) 中本来就取不到 mi. |
 | 5 arbipher 2015 年 4 月 9 日 1 稍微看了一下 首先把main函数改成： https://gist.github.com/arbipher/181c8456b04498e9c951 跑一下，发现结果是 1 2 2 推测是merge出了问题 然后把 merge(_elem, lo, mi, hi); 注释掉，再跑一下 结果是 1 3 2 证明merge肯定有错 也就是说你的代码把merge之前的1 3 2 marge成了1 2 2 merge函数我没有仔细看，但是你最后的for循环用的是有问题的，你在循环体内修改了循环参数 (很久不写C了不知道会有什么问题) 建议你改成while循环 |
Select Language