博文
深入分析qsort库函数（三）（原创）(2006-05-21 17:07:00)
摘要： 网上的文章当提到std::sort和qsort的区别时，通常把它们的性能差异归因于qsort的反引用开销，我们在这里通过实验来测试看看是不是这样，并且判断std::sort的算法是否有较之于qsort代码更优的性能，或者反过来。
测试用的源代码如下：
main.cpp 主函数所在的文件
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <algorithm>
#include "m_qsort.cpp"
#include "funcs.h"
using namespace std;
#define N 1000000
int comp(const void* a,const void* b)
{
return *(int*)a-*(int*)b;
}
void main()
{
int i,j,*a,*b;
clock_t st,et,tt[3]={0};
a=(int*)malloc(sizeof(int)*N);
b=(int*)malloc(sizeof(int)*N);
getchar();
for (i=0;i<10;i++)
{
m_srand((long)time(NULL));
for (j=0;j<N;j++) a[j]=m_rand();
memcpy(b,a,N*sizeof(int));
st=clock();
qsort(b,N,sizeof(int),comp);
et=clock();......
深入分析qsort库函数（二）（原创）(2006-05-20 00:07:00)
摘要： 在这篇文章，我们把目光投向C++ STL中的函数std::sort。可能有些朋友要奇怪了：不是要讲qsort函数吗，怎么讲起std::sort来了？其实，std::sort是一个改进版的qsort，我们通过分析std::sort，可以了解到qsort函数的优点和不足之处，方便我们更好地理解qsort函数的性质，从而深刻理解快速排序的算法思想。
我先介绍一下我分析的时候用的源代码。代码很简单，就是一个函数调用，排序随机生成的数组：
#include "stdlib.h"
#include "time.h"
#include <algorithm>
using namespace std;
int A[50];
int _tmain(int argc, _TCHAR* argv[])
{
int i;
srand(time(NULL));
for (i=0;i<50;i++) A[i]=rand();
std::sort(A,A+50);
return 0;
}
在std:sort这一行下一个断点，然后跟踪进去就可以看到如下代码：
template<class _RanIt> inline
void sort(_RanIt _First, _RanIt _Last)
{ // order [_First, _Last), using operator<
_Sort(_First, _Last, _Last - _First);
}
实际上sort又调用了_Sort函数，我们再跟进：
template<class _RanIt,
class _Diff> inline
void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal)
{ // order [......