c语言的qsort
^||void __fileDECL qsort (
void *base,
size_t num,
size_t width,
int (__fileDECL *comp)(const void *, const void *)
)
#endif /* __USE_CONTEXT */
{
char *lo, *hi; /* ends of sub-array currently sorting */
char *mid; /* points to middle of subarray */
char *loguy, *higuy; /* traveling pointers for partition step */
size_t size; /* size of the sub-array */
char *lostk[STKSIZ], *histk[STKSIZ];
int stkptr; /* stack for saving sub-array to be processed */
/* validation section */
_VALIDATE_RETURN_VOID(base != NULL || num == 0, EINVAL);
_VALIDATE_RETURN_VOID(width > 0, EINVAL);
_VALIDATE_RETURN_VOID(comp != NULL, EINVAL);
if (num < 2)
return; /* nothing to do */
stkptr = 0; /* initialize stack */
lo = (char *)base;
hi = (char *)base + width * (num-1); /* initialize limits */
/* this entry point is for pseudo-recursion calling: setting
lo and hi and jumping to here is like recursion, but stkptr is
preserved, locals aren't, so we preserve stuff on the stack */
recurse:
size = (hi - lo) / width + 1; /* number of el's to sort */
/* below a certain size, it is faster to use a O(n^2) sorting method */
if (size <= CUTOFF) {
__SHORTSORT(lo, hi, width, comp, context);
}
else {
/* First we pick a partitioning element. The efficiency of the
algorithm demands that we find one that is approximately the median
of the values, but also that we select one fast. We choose the
median of the first, middle, and last elements, to avoid bad
performance in the face of already sorted data, or data that is made
up of multiple sorted runs appended together. Testing shows that a
median-of-three algorithm provides better performance than simply
picking the middle element for the latter case. */
mid = lo + (size / 2) * width; /* find middle element */
/* Sort the first, middle, last elements into order */
if (__COMPARE(context, lo, mid) > 0) {
swap(lo, mid, width);
}
if (__COMPARE(context, lo, hi) > 0) {
swap(lo, hi, width);
}
if (__COMPARE(context, mid, hi) > 0) {
swap(mid, hi, width);
}
/* We now wish to partition the array into three pieces, one consisting
of elements <= partition element, one of elements equal to the
partition element, and one of elements > than it. This is done
below; comments indicate conditions established at every step. */
loguy = lo;
higuy = hi;
/* Note that higuy decreases and loguy increases on every iteration,
so loop must terminate. */
for (;;) {
/* lo <= loguy < hi, lo < higuy <= hi,
A[i] <= A[mid] for lo <= i <= loguy,
A[i] > A[mid] for higuy <= i < hi,
A[hi] >= A[mid] */
/* The doubled loop is to avoid calling comp(mid,mid), since some
existing comparison funcs don't work when passed the same
value for both pointers. */
if (mid > loguy) {
do {
loguy += width;
} while (loguy < mid && __COMPARE(context, loguy, mid) <= 0);
}
if (mid <= loguy) {
do {
loguy += width;
} while (loguy <= hi && __COMPARE(context, loguy, mid) <= 0);
}
/* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy,
either loguy > hi or A[loguy] > A[mid] */
do {
higuy -= width;
} while (higuy > mid && __COMPARE(context, higuy, mid) > 0);
/* lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi,
either higuy == lo or A[higuy] <= A[mid] */
if (higuy < loguy)
break;
/* if loguy > hi or higuy == lo, then we would have exited, so
A[loguy] > A[mid], A[higuy] <= A[mid],
loguy <= hi, higuy > lo */
swap(loguy, higuy, width);
/* If the partition element was moved, follow it. Only need
to check for mid == higuy, since before the swap,
A[loguy] > A[mid] implies loguy != mid. */
if (mid == higuy)
mid = loguy;
/* A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top
of loop is re-established */
}
/* A[i] <= A[mid] for lo <= i < loguy,
A[i] > A[mid] for higuy < i < hi,
A[hi] >= A[mid]
higuy < loguy
implying:
higuy == loguy-1
or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid] */
/* Find adjacent elements equal to the partition element. The
doubled loop is to avoid calling comp(mid,mid), since some
existing comparison funcs don't work when passed the same value
for both pointers. */
higuy += width;
if (mid < higuy) {
do {
higuy -= width;
} while (higuy > mid && __COMPARE(context, higuy, mid) == 0);
}
if (mid >= higuy) {
do {
higuy -= width;
} while (higuy > lo && __COMPARE(context, higuy, mid) == 0);
}
/* OK, now we have the following:
higuy < loguy
lo <= higuy <= hi
A[i] <= A[mid] for lo <= i <= higuy
A[i] == A[mid] for higuy < i < loguy
A[i] > A[mid] for loguy <= i < hi
A[hi] >= A[mid] */
/* We've finished the partition, now we want to sort the subarrays
[lo, higuy] and [loguy, hi].
We do the smaller one first to minimize stack usage.
We only sort arrays of length 2 or more.*/
if ( higuy - lo >= hi - loguy ) {
if (lo < higuy) {
lostk[stkptr] = lo;
histk[stkptr] = higuy;
++stkptr;
} /* save big recursion for later */
if (loguy < hi) {
lo = loguy;
goto recurse; /* do small recursion */
}
}
else {
if (loguy < hi) {
lostk[stkptr] = loguy;
histk[stkptr] = hi;
++stkptr; /* save big recursion for later */
}
if (lo < higuy) {
hi = higuy;
goto recurse; /* do small recursion */
}
}
}
/* We have sorted the array, except for any pending sorts on the stack.
Check if there are any, and do them. */
--stkptr;
if (stkptr >= 0) {
lo = lostk[stkptr];
hi = histk[stkptr];
goto recurse; /* pop subarray from stack */
}
else
return; /* all subarrays done */
}
② c语言 qsort
void
qsort(
void
*base,
size_t
num,
size_t
width,
int
(__cdecl
*compare
)(const
void
*elem1,
const
void
*elem2
)
);
qsort（quicksort）主要根据你给的比较条件给一个快速排序，主要是通过指针移动实现排序功能。排序之后的结果仍然放在原来数组中。
参数意义如下:
base:需要排序的目标数组开始地址
num:目标数组元素个数
width:目标数组中没一个元素长度
copare:函数指针，指向比较函数
给一个MSDN的例子:
#include
<stdlib.h>
#include
<string.h>
#include
<stdio.h>
int
compare(
const
void
*arg1,
const
void
*arg2
);
void
main(
int
argc,
char
**argv
)
{
int
i,
sz;
char*
dest[]
=
{"every",
"good",
"boy",
"deserves",
"favor"};
sz
=
5;
qsort(
(void
*)dest,
(size_t)sz,
sizeof(
char
*
),
compare
);
for(
i
=
0;
i
<
sz;
++i
)
printf(
"%s
",
dest[i]
);
printf(
"\n"
);
}
int
compare(
const
void
*arg1,
const
void
*arg2
)
{
return
_stricmp(
*
(
char**
)
arg1,
*
(
char**
)
arg2
);
}
③ C语言中qsort函数怎么用
#include<stdio.h>
#include<stdlib.h>
int cmp(const void*a,const void*b) // 排序规则（按降序排）
{
return *(int*)b-*(int*)a;
}
int main()
{
int a[]={1,2,3,4,5,6};
qsort(a,6,sizeof(int),cmp); // a是被排序的数组 6是排序元素回的个数 sizeof（int）是每答个元素所占的字节数 cmp是排序规则
for(int i=0;i<6;i++) //输出
printf("%d ",&a[i]);
return 0;
}
④ C语言关于qsort函数用法
第四个是回调函数的用法
由于qsort规定是int型函数，所以一定是int型，所以这点他不如c++的sort函数
const void *代表的是指针常量，即该指针只能指向a，不允许改变指向，保证了指针的安全性
（int *）a是强制将传进来的void 型指针转化为int型指针，*（int *）a的 * 是解析强制转化后int型指针a里面的int型数据，最后由return返回