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返回