[ZT]VC中的qsort源代码，值得学习

VBProFan · 发表于 2009-12-14 00:05:08

本帖最后由 VBProFan 于 2009-12-14 17:51 编辑

http://www.zaoxue.com/article/tech-55036.htm

/***
*qsort.c - quicksort algorithm; qsort() library function for sorting arrays
*
* Copyright (c) Microsoft Corporation. All rights reserved.
*
*Purpose:
* To implement the qsort() routine for sorting arrays.
*
*******************************************************************************/
#include <cruntime.h>
#include <stdlib.h>
#include <search.h>
#include <internal.h>
/* Always compile this module for speed, not size */
#pragmA[i] optimize("t", on)
/* prototypes for local routines */
static void __cdecl shortsort(char *lo, char *hi, size_t width,
int (__cdecl *comp)(const void *, const void *));
static void __cdecl swap(char *p, char *q, size_t width);
/* this parameter defines the cutoff between using quick sort and
insertion sort for arrays; arrays with lengths shorter or equal to the
below value use insertion sort */
#define CUTOFF 8 /* testing shows that this is good value */
/***
*qsort(base, num, wid, comp) - quicksort function for sorting arrays
*
*Purpose:
* quicksort the array of elements
* side effects: sorts in place
* maximum array size is number of elements times size of elements,
* but is limited by the virtual address space of the processor
*
*Entry:
* char *base = pointer to base of array
* size_t num = number of elements in the array
* size_t width = width in bytes of each array element
* int (*comp)() = pointer to function returning analog of strcmp for
* strings, but supplied by user for comparing the array elements.
* it accepts 2 pointers to elements and returns neg if 1<2, 0 if
* 1=2, pos if 1>2.
*
*Exit:
* returns void
*
*Exceptions:
*
*******************************************************************************/
/* sort the array between lo and hi (inclusive) */
#define STKSIZ (8*sizeof(void*) - 2)
void __cdecl qsort (
void *base,
size_t num,
size_t width,
int (__cdecl *comp)(const void *, const void *)
)
{
/* Note: the number of stack entries required is no more than
1 + log2(num), so 30 is sufficient for any array */
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 */
if (num < 2 || width == 0)
return; /* nothing to do */
stkptr = 0; /* initialize stack */
lo = 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[i] certain size, it is faster to use A[i] O(n^2) sorting method */
if (size <= CUTOFF) {
shortsort(lo, hi, width, comp);
}
else {
/* First we pick A[i] 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[i] 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 (comp(lo, mid) > 0) {
swap(lo, mid, width);
}
if (comp(lo, hi) > 0) {
swap(lo, hi, width);
}
if (comp(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 && comp(loguy, mid) <= 0);
}
if (mid <= loguy) {
do {
loguy += width;
} while (loguy <= hi && comp(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 && comp(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 && comp(higuy, mid) == 0);
}
if (mid >= higuy) {
do {
higuy -= width;
} while (higuy > lo && comp(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 */
}
/***
*shortsort(hi, lo, width, comp) - insertion sort for sorting short arrays
*
*Purpose:
* sorts the sub-array of elements between lo and hi (inclusive)
* side effects: sorts in place
* assumes that lo < hi
*
*Entry:
* char *lo = pointer to low element to sort
* char *hi = pointer to high element to sort
* size_t width = width in bytes of each array element
* int (*comp)() = pointer to function returning analog of strcmp for
* strings, but supplied by user for comparing the array elements.
* it accepts 2 pointers to elements and returns neg if 1<2, 0 if
* 1=2, pos if 1>2.
*
*Exit:
* returns void
*
*Exceptions:
*
*******************************************************************************/
static void __cdecl shortsort (
char *lo,
char *hi,
size_t width,
int (__cdecl *comp)(const void *, const void *)
)
{
char *p, *max;
/* Note: in assertions below, i and j are alway inside original bound of
array to sort. */
while (hi > lo) {
/* A[i] <= A[j] for i <= j, j > hi */
max = lo;
for (p = lo+width; p <= hi; p += width) {
/* A[i] <= A[max] for lo <= i < p */
if (comp(p, max) > 0) {
max = p;
}
/* A[i] <= A[max] for lo <= i <= p */
}
/* A[i] <= A[max] for lo <= i <= hi */
swap(max, hi, width);
/* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */
hi -= width;
/* A[i] <= A[j] for i <= j, j > hi, loop top condition established */
}
/* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
so array is sorted */
}
/***
*swap(a, b, width) - swap two elements
*
*Purpose:
* swaps the two array elements of size width
*
*Entry:
* char *a, *b = pointer to two elements to swap
* size_t width = width in bytes of each array element
*
*Exit:
* returns void
*
*Exceptions:
*
*******************************************************************************/
static void __cdecl swap (
char *a,
char *b,
size_t width
)
{
char tmp;
if ( A[i] != b )
/* Do the swap one character at A[i] time to avoid potential alignment
problems. */
while ( width-- ) {
tmp = *a;
*a++ = *b;
*b++ = tmp;
}
}

复制代码

acme_pjz · 发表于 2009-12-14 15:12:34

你装VC6的时候好象就可以选装C/C++运行库和MFC的源代码……粗略看了一下，好象用了median3和3路归并算法……

VBProFan · 发表于 2009-12-14 17:57:56

啊！不会吧？这些库函数的源码不是属于商业机密吗？
毕竟 VC 的开发小组还是付出了一些劳动的，不是简单地把地球上满天飞的C代码直接抄来的。。。

ps1：第一次粘贴时没有用 [code] 括起来，导致 [i] 全部丢失，刚才用 Editplus 把“A ”替换为“A[i] ”，不知道有没有替换错的地方，想直接用的朋友小心了；
ps2：这个函数的第四个参数让我见识到了 C 语言的恐怖之处，这是 BASIC 语言远远比不上的。

VBProFan · 发表于 2009-12-14 21:52:12

mid = lo + (size / 2) * width; /* find middle element */
/* Sort the first, middle, last elements into order */
if (comp(lo, mid) > 0) {
swap(lo, mid, width);
}
if (comp(lo, hi) > 0) {
swap(lo, hi, width);
}
if (comp(mid, hi) > 0) {
swap(mid, hi, width);
}

复制代码

核心都在这里了。果然是取中点作为初始关键字。而且就算所有关键字的值都相等，它也会将第一个数和中位数交换。

acme_pjz · 发表于 2009-12-14 23:47:50

3# VBProFan

这个函数的第四个参数让我见识到了 C 语言的恐怖之处，这是 BASIC 语言远远比不上的

哈哈

，就是这个参数，我用VB实现了……实现方法是Implements ISort，然后自定义比较函数

调用的时候写QuickSort xx,...,Me……我的那个实现是索引排序，不需要在内存中大规模移动数据……

这些库函数的源码不是属于商业机密吗？

C/C++都有ISO标准的，像qsort这种函数都是固定的吧，估计在任何一个C++里面都是一样的……

核心都在这里了。果然是取中点作为初始关键字。

这个不是真正的核心，只是Median3取中间值，核心在“Find adjacent elements equal to the partition element……”，即三路归并算法，所有等于pivot的值全部移到中间……你买一本数据结构看看就懂了，里面提到这个优化算法……

acme_pjz · 发表于 2009-12-16 12:21:22

LZ难道没有注意到VC2005里面就有C运行库的源代码？截图如下：

VBProFan · 发表于 2009-12-16 13:13:20

我一般都用 VC6，很少用 VC2005，除非是接手别人已经做好的项目。

那弱弱地问一下，VC6 也有吗？貌似安装过程中没有选择安源码这一项啊~~

acme_pjz · 发表于 2009-12-16 21:27:03

7# VBProFan

那就不知道了，我的VC6是绿色精简版，肯定没有

……不过企业版安装的时候有高级选项，我记得以前见过有源代码安装的……

VBProFan · 发表于 2009-12-16 22:10:18

哦，谢谢。下次我安装时注意看一下。。。

家鸽 · 发表于 2009-12-26 13:58:47

代码不错，谢谢分享~~~

		自动登录	找回密码
密码			立即注册

VBGood网站全文搜索

[ZT]VC中的qsort源代码，值得学习

评分