关于快速排序
假定元素的值不同，说明如何才能使快速排序在最坏的情况下以O(nlogn)时间运行？
我的想法：每次分割的时候都以中间的那个元素作为分割元素。
这样对么？还有没有其他的方法？

[解决办法]
你说的算法是折半插入排序，但好像这样的时间复杂度不是（nlog2n）吧，这个时间复杂度是快速排序的，

刚写了一个 ，供参考

C/C++ code

#include<stdio.h>void swap(int a[], int thi, int that){     int temp;    temp = a[thi]; a[thi]=a[that]; a[that]=temp;}int partition(int a[], int low, int high){     int i, j;    i = low+1;  j = high;    while( 1 )    {    for ( ; i<=j; i++ )  if (a[i] >= a[low]) break;        for ( ; i<=j; j-- )  if (a[j] < a[low]) break;        if ( i<j ) swap(a, i, j);        else // i > j        {    swap(a, low, j);  return j;    }    }}void quickSort(int a[], int low, int high){     int k;    if ( high > low)    {    k = partition(a, low, high);        quickSort(a, low, k-1);        quickSort(a, k+1, high);    }}void main (){    int n,j,i=0,a[100];    scanf ("%d",&n);    while (n--)        scanf ("%d",&a[i++]);    quickSort (a,0,i-1);    for (j=0;j<i-1;j++)        printf ("%d ",a[j]);    printf ("%d\n",a[j]);}
[解决办法]
C/C++ code
以下heap sort排序//heapSort.cpp#include <iostream>#include <cmath>using namespace std;#define NDEBUG//global viarableint heap_size;int length;//given the index i of a node,the indices of its parent,left child,right child can be computed .int PARENT(int i){return static_cast<int>(floor(i/2.2));}int LEFT(int i){return static_cast<int>(ceil(2*i+0.8));}int RIGHT(int i){return static_cast<int>(ceil(2*i+1.8));}//swap functionvoid swap(int& a,int& b){    int temp;    temp=a;    a=b;    b=temp;}//max heapify functionvoid MAX_HEAPIFY(int* A,int i){    int l=LEFT(i);    int r=RIGHT(i);    int largest=0;    if((l<=heap_size-1)&&(A[l]>A[i]))          largest=l;    else largest=i;    if ((r<=heap_size-1)&&(A[r]>A[largest]))        largest=r;    if (largest!=i){        swap(A[i],A[largest]);        MAX_HEAPIFY(A,largest);        }}//build -max-heap functionvoid BUILD_MAX_HEAP(int* A){     heap_size=length;    for(int i=static_cast<int>(floor(heap_size/2.2));i>=0;--i)        MAX_HEAPIFY(A,i);}//heap sort functionvoid HEAPSORT(int* A){    BUILD_MAX_HEAP(A);#ifndef NDEBUG    cout<<"the builded max heap is :"<<endl;    for(int j=0;j<length;++j)        cout<<A[j]<<" ";    cout<<endl;#endif    for(int i=heap_size-1;i>=0;--i){        swap(A[0],A[i]);        heap_size-=1;        MAX_HEAPIFY(A,0);    #ifndef NDEBUG        for(int j=0;j<heap_size;++j){            cout<<A[j]<<" ";        }        cout<<endl;#endif    }}//main functionvoid main(int argc,char** argv){    int a[]={4,1,3,2,16,9,10,14,8,7};    length=sizeof(a)/sizeof(a[0]);    cout<<"the older sequence is :";    for(int i=0;i<length;++i)        cout<<a[i]<<"  ";    cout<<endl;    HEAPSORT(a);    cout<<"heapsorted is :";    for(int i=0;i<length;++i)        cout<<a[i]<<"  ";    cout<<endl;    system("pause");}the older sequence is :4  1  3  2  16  9  10  14  8  7heapsorted is :1  2  3  4  7  8  9  10  14  16请按任意键继续. . .