博文
深入分析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(); tt[0]+=(et-st);
memcpy(b,a,N*sizeof(int)); &nb......
深入分析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 [_First, _Last), using operator< _Diff _Count; for (; _I......