嗯，感觉快排非常优秀了，虽然空间复杂度是O(logn)。 ---改正

[quote]嗯，感觉快排非常优秀了，虽然空间复杂度是O(nlogn)。[/quote]
空间复杂度为什么是O(nlogn)啊？

比较次数：Cmax=n/2（n-1）=n*n/2
我们设C（n）表示对长度为n的文件快速排序所需要的比较次数，所以C（n）也包括对长度为n的文件进行划分所需要的比较次数n-1，加上递归地对所得的左右两个子文件（长度<=n/2）快速排序的比较次数。假设文件长度n=2的k次方
比较次数C（n）<=n+2C(n/2)<=n+2[n/2+2C（n/4）]=2n+4C（n/4）
<=2n+4[n/4+2C(n/8)]=3n+8C(n/8)
<=.......
<=kn+mC（n/m）..................（m=2的k次方）
=nlog2n+nC(1)
=O(nlog2n)
............
所以时间复杂度O(nlog2n)

[quote][quote]嗯，感觉快排非常优秀了，虽然空间复杂度是O(nlogn)。[/quote]
空间复杂度为什么是O(nlogn)啊？[/quote]
空间复杂度是考虑到划分时候的递归调用的栈。

[quote]空间复杂度是考虑到划分时候的递归调用的栈。[/quote]
那应该是logn，即递归的深度。因为每一次递归没有使用辅助数组，只是一些零散变量。

补充一个五数(你可以设置任意大于2的整数)中值分割法选取枢纽元.
    Mark Allen Weiss在其著作<<数据结构与算法分析--c语言描述>>中对枢纽元的选取进行了分析.他认为使用第一个元素作为枢纽元是绝对糟糕的主义----我前面就是这样做的,呵呵.比较安全的做法是随机选取枢纽元,但是随机数的生成太"昂贵"了,会使效率降低.比较实用的是多元中值分割法(书上举了三数中值分割法的例子),枢纽元的最好位置是数组的中值,这样把数组分成两个相等的部分是最佳的.但是要寻找数组的中值可不是一件容易的事,我们只好折中一下,使用左端,右端和中心位置的三个元素的中值作为枢纽元.
    对于很小的数组(N<=20),快速排序不如插入排序好.所以我们可以设置一个长度上限max,当数组的长度大于max时,递归快速排序,否则使用插入排序.
template <class T>
void QuickSort(T a[], int len)
{
      Qsort(a, 0, len-1);
}

template <class T>
void Qsort(T a[], int low, int high)
{
      const int max = 5;//确定是否采用插入排序的数组长度上限 
    
      if (high-low >= max)
      {
            int k = Parttion(a, low, high);
            Qsort(a, low, k-1);
            Qsort(a, k+1, high);
      }
      else    //如果数组的元素很少（小于5个 ），使用折半插入排序 
          HalfInsertSort(a+low, high-low+1);    
}

template <class T>
void Swap(T &a, T &b)
{
    T temp = a;
    a = b;
    b = temp;
}

template <class T>
T Median(T a[], int low, int high)//取中间元素的值作为枢纽元素，同时对两端的元素排序 
{
    int mid = (low + high) / 2;

    if (a[low] > a[mid])
        Swap(a[low], a[mid]);
    if (a[low] > a[high])
        Swap(a[low], a[high]);
    if (a[mid] > a[high])
        Swap(a[mid], a[high]);
        
    Swap(a[mid], a[low+1]);//把枢纽元素放到数组的第2个位置 

    return a[low+1];
}

template <class T>
int Parttion(T a[], int low, int high)//根据枢纽元素分割数组 
{
    T pivot = Median(a, low, high); 
    int i = low + 1;
    int j = high;

    while (i < j)
    {
        while (a[++i] < pivot) {}
        while (a[--j] > pivot) {}
        if (i < j)
            Swap(a[i], a[j]);
    }
        
    Swap(a[j], a[low+1]); 

    return j;
}

template <class T>
void HalfInsertSort(T a[], int len)//折半插入排序 
{
      int i, j;
      int low, high, mid;
      T temp;
      for (i=1; i<len; i++)
      {
            temp = a[i];
            low = 0;
            high = i - 1;
            while (low <= high) //在a[low。。。high]中折半查找有序插入的位置
            {
                  mid = (low + high) / 2;
                  if (a[mid] > temp)
                        high = mid - 1;
                  else
                        low = mid + 1;
            } //while

            for (j=i-1; j>high; j--)//元素后移
                  a[j+1] = a[j];
            a[high+1] = temp; //插入
      }//for
}

楼主的程序体现了分类思想!
快排,有时我都认为快排还不如累堆(HEAP)排序!

堆排序的最差时间复杂度都能达到O(nlgn),但是平均情况不如快排好,而且还要使用辅助空间.所以总体来说还是快排好,而且程序简明易懂.

mark

#define NULL ( 0 )

void InsertionSort( int* start, int* end )
{
        int* p = NULL;
        int* q = NULL;
        int tmp;

        ++end;
        for ( p = start; p != end; ++p )
        {
                tmp = *p;
                for ( q = p; ( q != start ) && ( tmp < *(q - 1) ); --q )
                {
                        *q = *(q - 1);
                }
                *q = tmp;
        }
        return;
}

void swap( int* x, int* y )
{
        int tmp = *x;
        *x = *y;
        *y = tmp;
}

/* make that *a <= *b <= *c */
void Sort3( int* a, int* b, int* c) 
{
        if ( *b < *a )
        {
                swap( a, b );
        }
        if ( *c < *a )
        {
                swap( a, c );
        }
        if ( *c < *b )
        {
                swap( b, c );
        }
        return;
}

/* partition A and return the postion of pivot */
int Partition( int A[], int start, int end )
{
        int pivot;
        int i, j;
        int center = ( start + end ) / 2;

        Sort3( A + start, A + center, A + end );
        pivot = A[center];
        --end;   /* because now A[end] >= pivot */
        swap( A + center, A + end ); /* hide pivot */
        i = start;
        j = end;
        for ( ; ; )
        {
                for ( ++i; A[i] < pivot; ++i )
                {}
                for ( --j; A[j] > pivot; --j )
                {}
                if ( i < j )
                {
                        swap( A + i, A + j );
                }
                else
                {
                        break;
                }
        }
        swap( A + i, A + end ); /* restore pivot */
        return i;
}

#define  CUT_OFF  ( 10 )

void QSort( int A[], int start, int end )
{
        int pos_pivot;  /* position of pivot */

        if ( start + CUT_OFF <= end )
        {
                pos_pivot = Partition( A, start, end );

                QSort( A, start, pos_pivot - 1 );
                QSort( A, pos_pivot + 1, end );
        }
        else
        {
                InsertionSort( A + start, A + end );
        }
        return;
}

void QuickSort( int A[], int n )
{
        QSort( A, 0, n - 1 );
}

我也写了一个对整形数组的快排，思路基本上和weiss书中的一致。
对小数组采用插排，对于大数组采用快排，由CUT_OFF这个值来划分。
枢轴的选取是三数中值分割法。此法对于后面写分割函数Partition还有一些附加的好处，比如利用A[start]做监视哨防止j下越界，详见weiss书译本第183页开头处。