#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-04-09 10:29:41 +08:00 1
for (int i = 0; i < lb; i++) B[i] = _elem[i];
每次都从_elme的第一个元素开始复制到临时数组里面?这里应该是_elem[lo +i]之类的吧 后面没看。 找个小input用gdb或者lldb之类的调调吧…… |
2
SPACELAN 2015-04-09 12:53:07 +08:00
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-04-09 16:10:30 +08:00 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循环 |