快排之三

#include<iostream>      

#include<time.h>      

using namespace std;      

//遞歸實作快排      

void QuickSort(int pData[],int left,int right)      

{      

int i=left,j=right,key=pData[left];      

do      

{      

while(i<j&&pData[j]>key)      

j--;      

if(i<j)      

{      

pData[i]=pData[j];      

i++;      

}      

while(i<j&&pData[i]<key)      

i++;      

if(i<j)      

{      

pData[j]=pData[i];      

j--;      

}      

} while (i<j);      

pData[i]=key;        //循環結束時i==j      

if(left<j)      

QuickSort(pData,left,j-1);      

if(right>i)      

QuickSort(pData,i+1,right);      

}      

/*      

//非遞歸實作快排      

int QuickSort(int pData[],int left,int right)      

{      

int i=left,j=right,key=pData[left];      

do      

{      

while(i<j&&pData[j]>=key)j--;      

if(i<j){pData[i]=pData[j];i++;}      

while(i<j&&pData[i]<=key)i++;      

if(i<j){pData[j]=pData[i];j--;}      

} while (i<j);      

pData[i]=key;return i;      

}      

void NoRecQS(int pData[],int left,int right)      

{      

int stack[100][2],pivot,top=-1;            //建立輔助棧stack,pivot為軸心的意思      

if(left<right)      

{      

pivot=QuickSort(pData,left,right);      

if(left<pivot-1){top++;stack[top][0]=left;stack[top][1]=pivot-1;}      

if(right>pivot+1){top++;stack[top][0]=pivot+1;stack[top][1]=right;}      

while(top!=-1)    //top==-1表示棧空      

{      

left=stack[top][0];right=stack[top][1];    //之前已經保證stack[top][0]<stack[top][1],是以不必判斷left是否小于right      

pivot=QuickSort(pData,left,right);top--;//top--;退棧      

if(left<pivot-1){top++;stack[top][0]=left;stack[top][1]=pivot-1;}      

if(right>pivot+1){top++;stack[top][0]=pivot+1;stack[top][1]=right;}      

}      

}      

}      

*/      

int main()      

{      

int data[]={49,38,65,60,58,32,58,97,76,13,27};      

clock_t start,finish;      

double a;      

start=clock();      

//NoRecQS(data,0,10);      

QuickSort(data,0,10);      

finish=clock();      

a=(double)(finish-start)/CLOCKS_PER_SEC;      

printf("%f second needed\n",a);      

for(int i=0;i<11;i++)      

cout<<data[i]<<"   ";      

cout<<endl;      

return 0;      

}