昨天晚上一直想到现在才搞定。
修改了MERGE函数，现在的复杂度应该在O(nlgn)了。
[table=95%][tr][td][font=FixedSys][color=#000000][color=#ff9900]/* array1与array2必须是连续的空间,且array1在array2之前 */[/color]
[color=#0000ff]static void MERGE(void *array1, size_t nmemb1, void *array2, size_t nmemb2,
size_t size, int (*compar)(const void *, const void*))
{
void *i = array1, *j = array2, *k = i;
void *end1 = array1 + nmemb1 * size;
void *end2 = array2 + nmemb2 * size;
void *tmp_array = NULL;
int len;
while (i < end1 && j < end2) {
if (compar(i, j) > 0) {
if (tmp_array == NULL) {
len = end1 - i;
tmp_array = malloc(len);
memcpy(tmp_array, i, len);
i = tmp_array;
end1 = i + len;
}
memcpy(k, j, size);
j += size;
}
else {
if (tmp_array) {
memcpy(k, i, size);
}
i += size;
}
k += size;
if (j == end2 && tmp_array) {
memcpy(k, i, end1 - i);
}
}
if (tmp_array)
free(tmp_array);
}[/color][color=#0000cc][/color]
[color=#0000ff]void[/color] MERGE_SORT[color=#0000cc]([/color][color=#0000ff]void[/color] [color=#0000cc]*[/color]base[color=#0000cc],[/color] [color=#ff0000]size_t[/color] nmemb[color=#0000cc],[/color] [color=#ff0000]size_t[/color] size[color=#0000cc],[/color]
[color=#0000ff]int[/color] [color=#0000cc]([/color][color=#0000cc]*[/color]compar[color=#0000cc])[/color][color=#0000cc]([/color][color=#0000ff]const[/color] [color=#0000ff]void[/color] [color=#0000cc]*[/color][color=#0000cc],[/color] [color=#0000ff]const[/color] [color=#0000ff]void[/color] [color=#0000cc]*[/color][color=#0000cc])[/color][color=#0000cc])[/color]
[color=#0000cc]{[/color]
[color=#0000ff]if[/color] [color=#0000cc]([/color]nmemb [color=#0000cc]<[/color][color=#0000cc]=[/color] 0[color=#0000cc])[/color]
[color=#0000ff]return[/color][color=#0000cc];[/color]
[color=#0000ff]int[/color] depth [color=#0000cc]=[/color] [color=#0000cc]([/color][color=#0000ff]int[/color][color=#0000cc])[/color][color=#0000cc]([/color][color=#ff0000]ceil[/color][color=#0000cc]([/color]log2[color=#0000cc]([/color]nmemb[color=#0000cc])[/color][color=#0000cc])[/color][color=#0000cc])[/color][color=#0000cc];[/color]
[color=#0000ff]int[/color] num1 [color=#0000cc]=[/color] 1[color=#0000cc],[/color] num2 [color=#0000cc]=[/color] 1[color=#0000cc],[/color] tmp[color=#0000cc],[/color] remain_num[color=#0000cc];[/color]
[color=#0000ff]int[/color] node_num [color=#0000cc]=[/color] nmemb[color=#0000cc];[/color]
[color=#0000ff]int[/color] end_marge_flag[color=#0000cc],[/color] end_num[color=#0000cc];[/color]
[color=#0000ff]void[/color] [color=#0000cc]*[/color]array1 [color=#0000cc]=[/color] base[color=#0000cc],[/color] [color=#0000cc]*[/color]array2 [color=#0000cc]=[/color] base [color=#0000cc]+[/color] size[color=#0000cc];[/color]
remain_num [color=#0000cc]=[/color] 0[color=#0000cc];[/color]
end_num [color=#0000cc]=[/color] 1[color=#0000cc];[/color]
[color=#0000ff]while[/color] [color=#0000cc]([/color]depth[color=#0000cc])[/color] [color=#0000cc]{[/color]
tmp [color=#0000cc]=[/color] node_num [color=#0000cc]/[/color] 2[color=#0000cc];[/color]
end_marge_flag [color=#0000cc]=[/color] [color=#0000cc]![/color][color=#0000cc]([/color]node_num [color=#0000cc]%[/color] 2[color=#0000cc])[/color][color=#0000cc];[/color]
[color=#0000ff]for[/color] [color=#0000cc]([/color]array1 [color=#0000cc]=[/color] base[color=#0000cc],[/color] array2 [color=#0000cc]=[/color] base [color=#0000cc]+[/color] num1 [color=#0000cc]*[/color] size[color=#0000cc];[/color] tmp[color=#0000cc];[/color] tmp[color=#0000cc]-[/color][color=#0000cc]-[/color][color=#0000cc])[/color] [color=#0000cc]{[/color]
[color=#0000ff]if[/color] [color=#0000cc]([/color]end_marge_flag[color=#0000cc])[/color] [color=#0000cc]{[/color]
[color=#0000ff]if[/color] [color=#0000cc]([/color][color=#0000cc]![/color][color=#0000cc]([/color]tmp [color=#0000cc]-[/color] 1[color=#0000cc])[/color] [color=#0000cc]&[/color][color=#0000cc]&[/color] end_num[color=#0000cc])[/color] [color=#0000cc]{[/color]
num2 [color=#0000cc]=[/color] end_num[color=#0000cc];[/color]
end_num [color=#0000cc]=[/color] num1 [color=#0000cc]+[/color] num2[color=#0000cc];[/color]
[color=#0000cc]}[/color]
[color=#0000cc]}[/color]
[color=#ff0000]MERGE[/color][color=#0000cc]([/color]array1[color=#0000cc],[/color] num1[color=#0000cc],[/color] array2[color=#0000cc],[/color] num2[color=#0000cc],[/color] size[color=#0000cc],[/color] compar[color=#0000cc])[/color][color=#0000cc];[/color]
array1 [color=#0000cc]+[/color][color=#0000cc]=[/color] num1 [color=#0000cc]*[/color] size [color=#0000cc]+[/color] num2 [color=#0000cc]*[/color] size[color=#0000cc];[/color]
array2 [color=#0000cc]+[/color][color=#0000cc]=[/color] num2 [color=#0000cc]*[/color] size [color=#0000cc]+[/color] num1 [color=#0000cc]*[/color] size[color=#0000cc];[/color]
[color=#0000cc]}[/color]
num1 [color=#0000cc]<[/color][color=#0000cc]<[/color][color=#0000cc]=[/color] 1[color=#0000cc];[/color]
num2 [color=#0000cc]=[/color] num1[color=#0000cc];[/color]
node_num [color=#0000cc]=[/color] [color=#0000cc]([/color]node_num [color=#0000cc]%[/color] 2[color=#0000cc])[/color] [color=#0000cc]?[/color] node_num [color=#0000cc]/[/color] 2 [color=#0000cc]+[/color] 1 [color=#0000cc]:[/color] node_num [color=#0000cc]/[/color] 2[color=#0000cc];[/color]
depth[color=#0000cc]-[/color][color=#0000cc]-[/color][color=#0000cc];[/color]
[color=#0000cc]}[/color]
[color=#0000cc]}[/color][/color][/font][/td][/tr][/table]
[ 本帖最后由 cugb_cat 于 2008-3-11 17:06 编辑 ]
cugb_cat 回复于：2008-03-10 14:17:04
使用方法和qsort的使用方法一样。
cjaizss 回复于：2008-03-10 14:35:25
昨天拿sed不用e命令写了个加法.........
cugb_cat 回复于：2008-03-10 14:37:10
引用：原帖由 cjaizss 于 2008-3-10 14:35 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8059598&ptid=1063117]
昨天拿sed不用e命令写了个加法.........
sed不会用。。。。。
有时间得学学。
Edengundam 回复于：2008-03-10 15:35:52
引用：原帖由 cugb_cat 于 2008-3-10 14:17 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8059466&ptid=1063117]
使用方法和qsort的使用方法一样。
你的思路是不是先2个一组排序, 然后4个, 8个...这样进行??
可是qsort不能这样分解吧? 我只见过qsort的递归算法, 每次选取分界的元素后, 对两个子集继续排序. 这个过程感觉上不可逆...
没看你的代码, MergeSort函数的变量名看着头大...
cugb_cat 回复于：2008-03-10 15:41:28
引用：原帖由 Edengundam 于 2008-3-10 15:35 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8060069&ptid=1063117]
你的思路是不是先2个一组排序, 然后4个, 8个...这样进行??
可是qsort不能这样分解吧? 我只见过qsort的递归算法, 每次选取分界的元素后, 对两个子集继续排序. 这个过程感觉上不可逆...
没看你的代码, ...
不是，我是说用法和qsort一样，qsort是快速排序，我这个是合并排序，不一样的。
思路是从二叉树的树叶开始，向上一直到树根。
Edengundam 回复于：2008-03-10 16:09:07
引用：原帖由 cugb_cat 于 2008-3-10 15:41 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8060110&ptid=1063117]
不是，我是说用法和qsort一样，qsort是快速排序，我这个是合并排序，不一样的。
思路是从二叉树的树叶开始，向上一直到树根。
又看错了...看成了实现方法....最近精力严重不集中....
tyc611 回复于：2008-03-10 18:36:19
“非递归非栈，原地排序”，很不错，不知道是否仍是稳定的？（应该还是O(nlgn)吧？）
下去研究下
tyc611 回复于：2008-03-10 19:03:30
void *end1 = array1 + nmemb1 * size;
LZ，你的编译器不报错吗？:shock:
cugb_cat 回复于：2008-03-10 19:08:48
引用：原帖由 tyc611 于 2008-3-10 18:36 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8061197&ptid=1063117]
“非递归非栈，原地排序”，很不错，不知道是否仍是稳定的？（应该还是O(nlgn)吧？）
下去研究下
时间复杂度肯定还是O(nlgn)，只不过不使用递归和栈，省了不少空间和一些额外开销。
补充，我测试倒是没出错，还是要拜托大家多给测测:) :) :) :)
[ 本帖最后由 cugb_cat 于 2008-3-10 19:13 编辑 ]
cugb_cat 回复于：2008-03-10 19:09:55
引用：原帖由 tyc611 于 2008-3-10 19:03 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8061266&ptid=1063117]
void *end1 = array1 + nmemb1 * size;
LZ，你的编译器不报错吗？:shock:
没报错啊，
rainlx@rainlx:~$ gcc -v
Using built-in specs.
Target: i486-linux-gnu
Configured with: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --with-gxx-include-dir=/usr/include/c++/4.1.3 --program-suffix=-4.1 --enable-__cxa_atexit --enable-clocale=gnu --enable-libstdcxx-debug --enable-mpfr --enable-checking=release i486-linux-gnu
Thread model: posix
gcc version 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)
对了，用gcc编译，别用g++，这代码可能g++就出错了。
[ 本帖最后由 cugb_cat 于 2008-3-10 19:10 编辑 ]
tyc611 回复于：2008-03-10 19:14:30
引用：原帖由 tyc611 于 2008-3-10 18:36 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8061197&ptid=1063117]
“非递归非栈，原地排序”，很不错，不知道是否仍是稳定的？（应该还是O(nlgn)吧？）
下去研究下
看了下，LZ的算法仍是稳定的，但是合并操作中用时间换空间实现原地排序，增加了很多移动操作
tyc611 回复于：2008-03-10 19:15:37
引用：原帖由 cugb_cat 于 2008-3-10 19:08 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8061295&ptid=1063117]
时间复杂度肯定还是O(nlgn)，只不过不使用递归和栈，省了不少空间和一些额外开销。
补充，我测试倒是没出错，还是要拜托大家多给测测:) :) :) :)
时间复杂度已经不是了，你可不能把
memmove(i + step, i, j - i);
当作O(1)啊
tyc611 回复于：2008-03-10 19:18:06
引用：原帖由 cugb_cat 于 2008-3-10 19:09 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8061298&ptid=1063117]
没报错啊，
rainlx@rainlx:~$ gcc -v
Using built-in specs.
Target: i486-linux-gnu
Configured with: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr - ...
平时都不用C了，已经忘了C中怎么规定的，但C++中肯定是错的，因为一个指针类型加一个偏移量的运算结果与指针类型密切相关，而现在指针类型未知
cugb_cat 回复于：2008-03-10 19:29:23
引用：原帖由 tyc611 于 2008-3-10 19:15 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8061309&ptid=1063117]
时间复杂度已经不是了，你可不能把
memmove(i + step, i, j - i);
当作O(1)啊
memmove其实是两次memcpy操作。仔细琢磨起来，这样是比使用额外的空间增加了移动内存的次数，不过可以修改这个MERGE程序，只要符合原来的接口定义就行。
其实先MERGE到一个额外的空间，然后再copy到原来的空间，其实也挺费劲。具体的时间复杂度没细考虑。
cugb_cat 回复于：2008-03-10 19:30:12
引用：原帖由 tyc611 于 2008-3-10 19:18 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8061312&ptid=1063117]
平时都不用C了，已经忘了C中怎么规定的，但C++中肯定是错的，因为一个指针类型加一个偏移量的运算结果与指针类型密切相关，而现在指针类型未知
C中没问题的，呵呵，我都不会C＋＋。
那我改下吧，把类型强制转为char *就行了。
lalala 回复于：2008-03-10 19:51:58
LZ的merge用时间换空间了。。。。。。。
merge的时间复杂度就变成O(n^2)了，
用这个merge实现的merge sort就不是O(nlogn)了而是O(n^2logn)
[ 本帖最后由 lalala 于 2008-3-10 20:06 编辑 ]
cugb_cat 回复于：2008-03-10 20:04:16
引用：原帖由 lalala 于 2008-3-10 19:51 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8061364&ptid=1063117]
LZ的merge用时间换空间了。。。。。。。
这个问题我还的好好想想，多谢各位的提醒。
lalala 回复于：2008-03-10 20:09:29
我以前也想过这个，要使实现O(nlogn),就要实现merge的线性增长
cugb_cat 回复于：2008-03-11 17:09:27
修改了MERGE函数，详见1楼。降低了merge的时间复杂度，不过还是借助了额外的空间，但本着尽量少的使用额外空间的原则，只有在必需时才申请空间。
system888net 回复于：2008-03-11 17:16:32
:) 顶一下...
|
