问题描述
我有空闲时间并决定尝试实施标准库
qsort。这是一个非常简单的尝试，但它似乎工作。我必须指出效率对我来说根本不是问题，而且这可以说是纯粹的玩具。我很清楚这不是实现快速排序算法的最快方式，但我基本上只是想尝试使用
制作一个泛型函数。 。我测试了几个结构阵列
包含各种类型（这个，当然，并不意味着它是'b
正确，即使是远射:)。我将不胜感激任何建设性的
评论。下面的代码是一个片段。包含所有必需的头文件，并且uchar是unsigned char的typedef。
谢谢。
void do_swap_（void * a，void * b，size_t sz）
{
uchar t;
uchar * i = a;
uchar * j = b;
while（sz）{
t = * i;
* i ++ = * j ;
* j ++ = t;
--sz;
}
}
void quick_sort（void * v，size_t count，size_t sz，int（* cmp）（const void *，
const void *））
{
uchar * t = v;
uchar * x，* y;
uchar * r;
if（count）{
x = y = t;
r = t +（count-1）* sz;
for（; y< r ; y + = sz）
if（cmp（y，r）< 0）{
do_swap_（x，y，sz）;
x + = sz;
}
do_swap_（x，r，sz）;
quick_sort（t，（xt）/ sz， sz，cmp）;
quick_sort（x + sz，count-（xt）/ sz - 1，sz，cmp）;
}
}
I had some spare time and decided to try to implement the standard library
qsort. This is a pretty simpleminded attempt, but it seems to be working. I
have to point out that efficiency is not at all an issue for me, and this is
purely a toy, so to speak. I''m quite aware that this is not the quickest way
to implement the quicksort algorithm, but I basically just wanted to try to
make a "generic function". I tested it with a few arrays of structures
containing all sorts of types (this, ofcourse, doesn''t mean that it''s
correct, even by a long shot :). I would appreciate any and all constructive
comments. The code below is a snippet. All the necessary headers are
included and uchar is a typedef for unsigned char.
Thank you.
void do_swap_(void *a, void *b, size_t sz)
{
uchar t;
uchar *i = a;
uchar *j = b;
while (sz) {
t = *i;
*i++ = *j;
*j++ = t;
--sz;
}
}
void quick_sort(void *v, size_t count, size_t sz, int (*cmp)(const void *,
const void *))
{
uchar *t = v;
uchar *x, *y;
uchar *r;
if (count) {
x = y = t;
r = t+(count-1)*sz;
for(; y<r; y += sz)
if (cmp(y, r)<0) {
do_swap_(x, y, sz);
x += sz;
}
do_swap_(x, r, sz);
quick_sort(t, (x-t)/sz, sz, cmp);
quick_sort(x+sz, count-(x-t)/sz - 1, sz, cmp);
}
}
推荐答案
-
pete
--
pete
如果count == 1，算法无论如何做比较。我知道你
在这里不是真正的效率，但这似乎有点
奇怪。
如果sz == 0，各种奇怪和令人讨厌的事情都会发生，但是打电话的人要求它。
似乎这个算法可能最终会递归很多。
这可能是大量数据的问题。
这里值得一试的是你的算法运作得多好
带有伪造比较例程（例如，一个总是返回-1，或者
，其中cmp（a，b）不能保证等于-cmp（b，a））。一些
的实现最终会在这种
的情况下超出传入的数组。
[*]技术说明：bogosort通过创建来运行所有可能的
排序数组的订单，确定订单中有多少元素
，并返回元素数量最少的订单
按顺序排序并返回第一个。在其他
的单词中，它将N个元素的排序问题转化为排序之一
N！元素。
递归bogosort使用bogosort按可能的顺序排序
元素数量不按顺序，从而解决了问题
将N个元素排序为排序N !!!!!!!!!!!!!!!!!!!!!!!!!! ....
元素。 Bogosorts通常包括其他性能浪费
代码，例如：
while（malloc（INT_MAX））fork（）;
因为它们永远不会无论如何都要完成。
Gordon L. Burditt
If count == 1, the algorithm does a compare anyway. I know you
weren''t going for real efficiency here, but this seems a bit
strange.
If sz == 0, various wierd and obnoxious things will happen, but
the caller IS asking for it.
It seems like this algorithm could end up recursing a lot.
This could be a problem with large amounts of data.
One thing worth checking here is how well your algorithm will operate
with a bogus compare routine (e.g. one which always returns -1, or
one for which cmp(a,b) is not guaranteed to equal -cmp(b,a) ). Some
implementations end up going outside the passed-in array in such
circumstances.
[*] Technical note: a bogosort operates by creating all possible
orders of the sorted array, determining how many elements are out
of order, and returns the order with the least number of elements
out of order by sorting them and returning the first one. In other
words, it turns the problem of sorting N elements into one of sorting
N! elements.
A recursive bogosort uses bogosort to sort the possible orders by
number of elements out of order, thereby turning the problem of
sorting N elements into one of sorting N!!!!!!!!!!!!!!!!!!!!!!!!!!....
elements. Bogosorts typically include other performance-wasting
code such as:
while (malloc(INT_MAX)) fork();
since they will never finish anyway.
Gordon L. Burditt
qsort（）不需要实现任何特定的排序算法。这里值得检查的一件事是你的算法在伪造比较程序中的运行情况如何（例如总是返回-1的那个，或者是一个cmp（a，b）不是保证等于-cmp（b，a））。
在这种情况下，某些实现最终会超出传入的
数组。
qsort() is not required to implement any particular sort algorithm.
It''s just supposed to sort. One thing worth checking here is how well your algorithm will operate
with a bogus compare routine (e.g. one which always returns -1, or
one for which cmp(a,b) is not guaranteed to equal -cmp(b,a) ).
Some implementations end up going outside the passed-in
array in such circumstances.
具有伪造比较例程的qsort的行为未定义，
那么重点是什么？
-
pete
The behavior of qsort with a bogus compare routine, is undefined,
so what''s the point?
--
pete
这篇关于尝试qsort实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！