qsort源码
‘壹’ C和C++如何混合编程
在用C++的项目源码中，经常会不可避免的会看到下面的代码：
1
#ifdef __cplusplus
2
extern "C" {
3
#endif
4
5
/*...*/
6
7
#ifdef __cplusplus
8
}
9
#endif
它到底有什么用呢，你知道吗？而且这样的问题经常会出现在面试or笔试中。下面我就从以下几个方面来介绍它：
1、#ifdef _cplusplus/#endif _cplusplus及发散
2、extern "C"
2.1、extern关键字
2.2、"C"
2.3、小结extern "C"
3、C和C++互相调用 4、C和C++混合调用特别之处函数指针
3.1、C++的编译和连接
3.2、C的编译和连接
3.3、C++中调用C的代码
3.4、C中调用C++的代码
1、#ifdef _cplusplus/#endif _cplusplus及发散
在介绍extern "C"之前，我们来看下#ifdef
_cplusplus/#endif
_cplusplus的作用。很明显#ifdef/#endif、#ifndef/#endif用于条件编译，#ifdef
_cplusplus/#endif
_cplusplus——表示如果定义了宏_cplusplus，就执行#ifdef/#endif之间的语句，否则就不执行。
在这里为什么需要#ifdef _cplusplus/#endif
_cplusplus呢？因为c语言中不支持extern "C"声明，如果你明白extern
"C"的作用就知道在C中也没有必要这样做，这就是条件编译的作用！在.c文件中包含了extern "C"时会出现编译时错误。
既然说到了条件编译，我就介绍它的一个重要应用——避免重复包含头文件。还记得腾讯笔试就考过这个题目，给出类似下面的代码（下面是我最近在研究的一个开源web服务器——Mongoose的头文件mongoose.h中的一段代码）：
01
#ifndef MONGOOSE_HEADER_INCLUDED
02
#define MONGOOSE_HEADER_INCLUDED
03
04
#ifdef __cplusplus
05
extern "C" {
06
#endif /* __cplusplus */
07
08
/*.................................
09
* do something here
10
*.................................
11
*/
12
13
#ifdef __cplusplus
14
}
15
#endif /* __cplusplus */
16
17
#endif /* MONGOOSE_HEADER_INCLUDED */
然后叫你说明上面宏#ifndef/#endif的作用？为了解释一个问题，我们先来看两个事实：
这个头文件mongoose.h可能在项目中被多个源文件包含（#include
"mongoose.h"），而对于一个大型项目来说，这些冗余可能导致错误，因为一个头文件包含类定义或inline函数，在一个源文件中mongoose.h可能会被#include两次（如，a.h头文件包含了mongoose.h，而在b.c文件中#include
a.h和mongoose.h）——这就会出错（在同一个源文件中一个结构体、类等被定义了两次）。
从逻辑观点和减少编译时间上，都要求去除这些冗余。然而让程序员去分析和去掉这些冗余，不仅枯燥且不太实际，最重要的是有时候又需要这种冗余来保证各个模块的独立。
为了解决这个问题，上面代码中的
#ifndef MONGOOSE_HEADER_INCLUDED
#define MONGOOSE_HEADER_INCLUDED
/*……………………………*/
#endif /* MONGOOSE_HEADER_INCLUDED */
就起作用了。如果定义了MONGOOSE_HEADER_INCLUDED，#ifndef/#endif之间的内容就被忽略掉。因此，编译时第一次看到mongoose.h头文件，它的内容会被读取且给定MONGOOSE_HEADER_INCLUDED一个值。之后再次看到mongoose.h头文件时，MONGOOSE_HEADER_INCLUDED就已经定义了，mongoose.h的内容就不会再次被读取了。
2、extern "C"
首先从字面上分析extern "C"，它由两部分组成——extern关键字、"C"。下面我就从这两个方面来解读extern "C"的含义。
2.1、extern关键字
在一个项目中必须保证函数、变量、枚举等在所有的源文件中保持一致，除非你指定定义为局部的。首先来一个例子：
1
//file1.c:
2
int x=1;
3
int f(){do something here}
4
//file2.c:
5
extern int x;
6
int f();
7
void g(){x=f();}
在file2.c中g()使用的x和f()是定义在file1.c中的。extern关键字表明file2.c中x，仅仅是一个变量的声明，其并不是在定义变量x，并未为x分配内存空间。变量x在所有模块中作为一种全局变量只能被定义一次，否则会出现连接错误。但是可以声明多次，且声明必须保证类型一致，如：
1
//file1.c:
2
int x=1;
3
int b=1;
4
extern c;
5
//file2.c:
6
int x;// x equals to default of int type 0
7
int f();
8
extern double b;
9
extern int c;
在这段代码中存在着这样的三个错误：
x被定义了两次
b两次被声明为不同的类型
c被声明了两次，但却没有定义
回到extern关键字，extern是C/C++语言中表明函数和全局变量作用范围（可见性）的关键字，该关键字告诉编译器，其声明的函数和变量可以在本模块或其它模块中使用。通常，在模块的头文件中对本模块提供给其它模块引用的函数和全局变量以关键字extern声明。例如，如果模块B欲引用该模块A中定义的全局变量和函数时只需包含模块A的头文件即可。这样，模块B中调用模块A中的函数时，在编译阶段，模块B虽然找不到该函数，但是并不会报错；它会在连接阶段中从模块A编译生成的目标代码中找到此函数。
与extern对应的关键字是 static，被它修饰的全局变量和函数只能在本模块中使用。因此，一个函数或变量只可能被本模块使用时，其不可能被extern “C”修饰。
2.2、"C"
典型的，一个C++程序包含其它语言编写的部分代码。类似的，C++编写的代码片段可能被使用在其它语言编写的代码中。不同语言编写的代码互相调用是困难的，甚至是同一种编写的代码但不同的编译器编译的代码。例如，不同语言和同种语言的不同实现可能会在注册变量保持参数和参数在栈上的布局，这个方面不一样。
为了使它们遵守统一规则，可以使用extern指定一个编译和连接规约。例如，声明C和C++标准库函数strcyp()，并指定它应该根据C的编译和连接规约来链接：
1
extern "C" char* strcpy(char*,const char*);
注意它与下面的声明的不同之处：
1
extern char* strcpy(char*,const char*);
下面的这个声明仅表示在连接的时候调用strcpy()。
extern "C"指令非常有用，因为C和C++的近亲关系。注意：extern "C"指令中的C，表示的一种编译和连接规约，而不是一种语言。C表示符合C语言的编译和连接规约的任何语言，如Fortran、assembler等。
还有要说明的是，extern "C"指令仅指定编译和连接规约，但不影响语义。例如在函数声明中，指定了extern "C"，仍然要遵守C++的类型检测、参数转换规则。
再看下面的一个例子，为了声明一个变量而不是定义一个变量，你必须在声明时指定extern关键字，但是当你又加上了"C"，它不会改变语义，但是会改变它的编译和连接方式。
如果你有很多语言要加上extern "C"，你可以将它们放到extern "C"{ }中。
2.3、小结extern "C"
通过上面两节的分析，我们知道extern "C"的真实目的是实现类C和C++的混合编程。在C++源文件中的语句前面加上extern "C"，表明它按照类C的编译和连接规约来编译和连接，而不是C++的编译的连接规约。这样在类C的代码中就可以调用C++的函数or变量等。（注：我在这里所说的类C，代表的是跟C语言的编译和连接方式一致的所有语言）
3、C和C++互相调用
我们既然知道extern "C"是实现的类C和C++的混合编程。下面我们就分别介绍如何在C++中调用C的代码、C中调用C++的代码。首先要明白C和C++互相调用，你得知道它们之间的编译和连接差异，及如何利用extern "C"来实现相互调用。
3.1、C++的编译和连接
C++是一个面向对象语言（虽不是纯粹的面向对象语言），它支持函数的重载，重载这个特性给我们带来了很大的便利。为了支持函数重载的这个特性，C++编译器实际上将下面这些重载函数：
1
void print(int i);
2
void print(char c);
3
void print(float f);
4
void print(char* s);
编译为：
1
_print_int
2
_print_char
3
_print_float
4
_pirnt_string
这样的函数名，来唯一标识每个函数。注：不同的编译器实现可能不一样，但是都是利用这种机制。所以当连接是调用print(3)时，它会去查找_print_int(3)这样的函数。下面说个题外话，正是因为这点，重载被认为不是多态，多态是运行时动态绑定（“一种接口多种实现”），如果硬要认为重载是多态，它顶多是编译时“多态”。
C++中的变量，编译也类似，如全局变量可能编译g_xx，类变量编译为c_xx等。连接是也是按照这种机制去查找相应的变量。
3.2、C的编译和连接
C语言中并没有重载和类这些特性，故并不像C++那样print(int
i)，会被编译为_print_int，而是直接编译为_print等。因此如果直接在C++中调用C的函数会失败，因为连接是调用C中的print(3)时，它会去找_print_int(3)。因此extern
"C"的作用就体现出来了。
3.3、C++中调用C的代码
假设一个C的头文件cHeader.h中包含一个函数print(int i)，为了在C++中能够调用它，必须要加上extern关键字（原因在extern关键字那节已经介绍）。它的代码如下：
1
#ifndef C_HEADER
2
#define C_HEADER
3
4
extern void print(int i);
5
6
#endif C_HEADER
相对应的实现文件为cHeader.c的代码为：
1
#include <stdio.h>
2
#include "cHeader.h"
3
void print(int i)
4
{
5
printf("cHeader %d\n",i);
6
}
现在C++的代码文件C++.cpp中引用C中的print(int i)函数：
1
extern "C"{
2
#include "cHeader.h"
3
}
4
5
int main(int argc,char** argv)
6
{
7
print(3);
8
return 0;
9
}
执行程序输出：
3.4、C中调用C++的代码
现在换成在C中调用C++的代码，这与在C++中调用C的代码有所不同。如下在cppHeader.h头文件中定义了下面的代码：
1
#ifndef CPP_HEADER
2
#define CPP_HEADER
3
4
extern "C" void print(int i);
5
6
#endif CPP_HEADER
相应的实现文件cppHeader.cpp文件中代码如下：
1
#include "cppHeader.h"
2
3
#include <iostream>
4
using namespace std;
5
void print(int i)
6
{
7
cout<<"cppHeader "<<i<<endl;
8
}
在C的代码文件c.c中调用print函数：
1
extern void print(int i);
2
int main(int argc,char** argv)
3
{
4
print(3);
5
return 0;
6
}
注意在C的代码文件中直接#include "cppHeader.h"头文件，编译出错。而且如果不加extern int print(int i)编译也会出错。
4、C和C++混合调用特别之处函数指针
当我们C和C++混合编程时，有时候会用一种语言定义函数指针，而在应用中将函数指针指向另一中语言定义的函数。如果C和C++共享同一中编译和连接、函数调用机制，这样做是可以的。然而，这样的通用机制，通常不然假定它存在，因此我们必须小心地确保函数以期望的方式调用。
而且当指定一个函数指针的编译和连接方式时，函数的所有类型，包括函数名、函数引入的变量也按照指定的方式编译和连接。如下例：
01
typedef int (*FT) (const void* ,const void*);//style of C++
02
03
extern "C"{
04
typedef int (*CFT) (const void*,const void*);//style of C
05
void qsort(void* p,size_t n,size_t sz,CFT cmp);//style of C
06
}
07
08
void isort(void* p,size_t n,size_t sz,FT cmp);//style of C++
09
void xsort(void* p,size_t n,size_t sz,CFT cmp);//style of C
10
11
//style of C
12
extern "C" void ysort(void* p,size_t n,size_t sz,FT cmp);
13
14
int compare(const void*,const void*);//style of C++
15
extern "C" ccomp(const void*,const void*);//style of C
16
17
void f(char* v,int sz)
18
{
19
//error,as qsort is style of C
20
//but compare is style of C++
21
qsort(v,sz,1,&compare);
22
qsort(v,sz,1,&ccomp);//ok
23
24
isort(v,sz,1,&compare);//ok
25
//error,as isort is style of C++
26
//but ccomp is style of C
27
isort(v,sz,1,&ccopm);
28
}
注意：typedef int (*FT) (const void* ,const void*)，表示定义了一个函数指针的别名FT，这种函数指针指向的函数有这样的特征：返回值为int型、有两个参数，参数类型可以为任意类型的指针（因为为void*）。
最典型的函数指针的别名的例子是，信号处理函数signal，它的定义如下：
1
typedef void (*HANDLER)(int);
2
HANDLER signal(int ,HANDLER);
上面的代码定义了信函处理函数signal，它的返回值类型为HANDLER，有两个参数分别为int、HANDLER。 这样避免了要这样定义signal函数：
1
void (*signal (int ,void(*)(int) ))(int)
比较之后可以明显的体会到typedef的好处。
‘贰’ c语言如何用qsort对二维数组排序
在C语言中，二维数组按行存储，对每一行排序很方便，可以把每一行当成一个一维数运薯组，使用排序函数直接进行排序。
然而对每一列进行排序，就不能直接当成一维数组进行排序。但是仍然可以把第j列a[0...M-1][j]在逻辑上当成一维数组进行排序，下面以使用冒泡排序为例对友腔其排序。
对二维数组按列排序后，进一步展示了如何调用快速排序函数按行进行排序。
程序源码：
#include<stdio.h>#include<stdlib.h>#defineM3#defineN3//输出二维数组的函数voidprint(inta[][N]){inti,j;for(i=0;i<M;i++){for(j=0;j<N;j++){printf("%d",a[i][j]);}printf(" ");}}//qsort的cmp函数intcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}intmain(intargc,char*argv){inta[M][N]={3,2,1,9,8,7,6,5,4};printf("按列排序前的二维数组是： ");print(a);printf(" ");intj;for(j=0;j<N;j++)//对每一列进行升序排序{//对第j列进行排序intm,n;intt;for(m=M-1;m>0;m--){for(n=0;n<m;n++){if(a[n][j]>a[n+1][j]){旁告者t=a[n][j];a[n][j]=a[n+1][j];a[n+1][j]=t;}}}}printf("按列排序后二维数组变为： ");print(a);printf(" ");//对按列排序后的二维数组按行升序排序（调用快速排序函数）inti;for(i=0;i<M;i++){qsort(a[i],N,sizeof(a[i][0]),cmp);}printf("按列排序后再按行排序后二维数组变为： ");print(a);printf(" ");system("pause");return0;}
编译运行后的结果如下：
‘叁’ c库函数源码
不是你表达不清，也许只是你根本不想仔细看一睛VC下面目录的源码，事实上就是有的。后附其中的qsort.c，以证明所言不虚。
VC的库是提供源码的，这东西也不值钱。
X:\Program Files\Microsoft Visual Studio\VCXX\CRT\SRC
注意有些可能本身是用汇编写的。
/***
*qsort.c - quicksort algorithm; qsort() library function for sorting arrays
*
* Copyright (c) 1985-1997, Microsoft Corporation. All rights reserved.
*
*Purpose:
* To implement the qsort() routine for sorting arrays.
*
*******************************************************************************/
#include <cruntime.h>
#include <stdlib.h>
#include <search.h>
/* prototypes for local routines */
static void __cdecl shortsort(char *lo, char *hi, unsigned width,
int (__cdecl *comp)(const void *, const void *));
static void __cdecl swap(char *p, char *q, unsigned int 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
*
*Entry:
* char *base = pointer to base of array
* unsigned num = number of elements in the array
* unsigned 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) */
void __cdecl qsort (
void *base,
unsigned num,
unsigned width,
int (__cdecl *comp)(const void *, const void *)
)
{
char *lo, *hi; /* ends of sub-array currently sorting */
char *mid; /* points to middle of subarray */
char *loguy, *higuy; /* traveling pointers for partition step */
unsigned size; /* size of the sub-array */
char *lostk[30], *histk[30];
int stkptr; /* stack for saving sub-array to be processed */
/* Note: the number of stack entries required is no more than
1 + log2(size), so 30 is sufficient for any array */
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
prserved, 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);
}
else {
/* First we pick a partititioning 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. Using
the first one proces bad performace if the array is already
sorted, so we use the middle one, which would require a very
wierdly arranged array for worst case performance. Testing shows
that a median-of-three algorithm does not, in general, increase
performance. */
mid = lo + (size / 2) * width; /* find middle element */
swap(mid, lo, width); /* swap it to beginning of array */
/* We now wish to partition the array into three pieces, one
consisiting of elements <= partition element, one of elements
equal to the parition element, and one of element >= to it. This
is done below; comments indicate conditions established at every
step. */
loguy = lo;
higuy = hi + width;
/* Note that higuy decreases and loguy increases on every iteration,
so loop must terminate. */
for (;;) {
/* lo <= loguy < hi, lo < higuy <= hi + 1,
A[i] <= A[lo] for lo <= i <= loguy,
A[i] >= A[lo] for higuy <= i <= hi */
do {
loguy += width;
} while (loguy <= hi && comp(loguy, lo) <= 0);
/* lo < loguy <= hi+1, A[i] <= A[lo] for lo <= i < loguy,
either loguy > hi or A[loguy] > A[lo] */
do {
higuy -= width;
} while (higuy > lo && comp(higuy, lo) >= 0);
/* lo-1 <= higuy <= hi, A[i] >= A[lo] for higuy < i <= hi,
either higuy <= lo or A[higuy] < A[lo] */
if (higuy < loguy)
break;
/* if loguy > hi or higuy <= lo, then we would have exited, so
A[loguy] > A[lo], A[higuy] < A[lo],
loguy < hi, highy > lo */
swap(loguy, higuy, width);
/* A[loguy] < A[lo], A[higuy] > A[lo]; so condition at top
of loop is re-established */
}
/* A[i] >= A[lo] for higuy < i <= hi,
A[i] <= A[lo] for lo <= i < loguy,
higuy < loguy, lo <= higuy <= hi
implying:
A[i] >= A[lo] for loguy <= i <= hi,
A[i] <= A[lo] for lo <= i <= higuy,
A[i] = A[lo] for higuy < i < loguy */
swap(lo, higuy, width); /* put partition element in place */
/* OK, now we have the following:
A[i] >= A[higuy] for loguy <= i <= hi,
A[i] <= A[higuy] for lo <= i < higuy
A[i] = A[lo] for higuy <= i < loguy */
/* We've finished the partition, now we want to sort the subarrays
[lo, higuy-1] and [loguy, hi].
We do the smaller one first to minimize stack usage.
We only sort arrays of length 2 or more.*/
if ( higuy - 1 - lo >= hi - loguy ) {
if (lo + width < higuy) {
lostk[stkptr] = lo;
histk[stkptr] = higuy - width;
++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 + width < higuy) {
hi = higuy - width;
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
* unsigned 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,
unsigned 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
* unsigned width = width in bytes of each array element
*
*Exit:
* returns void
*
*Exceptions:
*
*******************************************************************************/
static void __cdecl swap (
char *a,
char *b,
unsigned width
)
{
char tmp;
if ( a != b )
/* Do the swap one character at a time to avoid potential alignment
problems. */
while ( width-- ) {
tmp = *a;
*a++ = *b;
*b++ = tmp;
}
}
‘肆’ qsort源码在linux哪个目录
linux没有这个源码的。
楼码备主遇到的这个问题，可能不是太准确，迟吵毁 最好是可以帮忙楼主看碰此看
能否私聊呢
‘伍’ C++求助，摘花生问题
acm?....
貌似poj上有改渗橘这道题。。
http://acm.pku.e.cn/JudgeOnline/problem?id=1928
讲解来看看poj的论坛吧喊桥
http://acm.pku.e.cn/JudgeOnline/bbs?problem_id=1928
我的源码：
#include<stdio.h>
#include<stdlib.h>
int w,h,t;
struct s_cell
{
int x;
int y;
int num;
}map[52*52];
void putin(void);
void sort(void);
int my_sort(const void* e1,const void *e2);
int count(void);
int getneeded(int mp);
int getfact(int mp);
int main(void)
{
int times;
scanf("%d",×);
for(int i=0;i<times;i++)
{
scanf("%d%d%d",&h,&w,&t);
putin();
sort();
int num=count();
printf("%d\n"核团,num);
}
return 0;
}
void putin(void)
{
int i=0;
for(int y=0;y<h;y++)
for(int x=0;x<w;x++,i++)
scanf("%d",&map[i].num),map[i].x=x,map[i].y=y;
}
void sort(void)
{
qsort(map,h*w,sizeof(map[0]),my_sort);
}
int my_sort(const void* e1,const void *e2)
{
return ((s_cell *)e2)->num-((s_cell *)e1)->num;
}
int count(void)
{
int num=0;
int mp=0;
while(1)
{
int needed=getneeded(mp);
if(t<needed)
break;
t-=getfact(mp);
num+=map[mp].num;
if(map[mp].num==0)
break;
mp++;
}
return num;
}
int getneeded(int mp)
{
if(mp==0)
{
return map[0].y+1 + 1 + map[0].y+1;
}
else
{
return abs(map[mp].x-map[mp-1].x)+abs(map[mp].y-map[mp-1].y) + 1 + map[mp].y+1;
}
}
int getfact(int mp)
{
if(mp==0)
{
return map[0].y+1 + 1;
}
else
{
return abs(map[mp].x-map[mp-1].x)+abs(map[mp].y-map[mp-1].y) +1;
}
}
‘陆’ 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在哪个文件里
qsort是C标准库函数，包含在头文件stdlib.h中。在ISO C++中为std::qsort，包含在文件cstdlib中。
#include<cstdlib>之后唤拍，可以直接调用std::qsort或using namespace std;然后再调用qsort。
注意库文件只有声明。具体实现在链接库文件中，视编译虚饥环境而定（例如Microsoft C Runtime Library的MSVCP60.dll、MSVCP71.dll、差链返MSVCP90.dll等）。且只有二进制代码，没有源代码。可以反汇编相关文件得到一些细节。
如果需要源代码，可以Google“qsort 源码”查找相关信息。
----
[原创回答团]