快速排序基本思想：選取A為某個(gè)元素,，例如說t=A(s),，然后將其它的元素重新排列，使A(1:n)中的所有在t以前的元素都小于或等于t,，而所有在t之后的元素都大于或等于t,。

//語言：c++
//目的：比較兩個(gè)排序算法的時(shí)間復(fù)雜度
//原代碼：
//Insertionsort
int *Insertionsort(int *A,int n)
{
 int j,item,i;
 for(j=2;j<=n;j++)
 {
  item=A[j];
      i=j-1;
  
  while (item<A[i])
  {
   A[i+1]=A[i];
   i--;
  }
  A[i+1]=item;
 }
 return A;
}//insertionsort
//quicksort
int Quickpass(int R[],int  low,int  high)
{
 int down,up; //initialize  flag
 down=low;up=high;R[0]=R[low]; //put benchmark record into R[0]
 while (down<up)
 {
  while((down<up)&&(R[up]>=R[0])) //scan from right to left
   up--;
  if(down<up)
   R[down++]=R[up];
  while((down<up)&&(R[down]<=R[0]))//scan from left to right
   down++;
  if(down<up)
   R[up--]=R[down];
 }
 R[down]=R[0];
 return down;
}//one time of sortion

int  *Quicksort(int R[],int low,int high)
{
 int mid;
 if (low<high)
 {
  mid=Quickpass(R,low,high);
  Quicksort(R,low,mid-1);
  Quicksort(R,mid+1,high);
 }
 return R;
}//quicksort
#include<iostream.h>
#include<time.h>
#include<stdlib.h>
//////main function
void main()
{
 clock_t start,end;
 float elapsed1; //time of quicksort
 float elapsed2; //time of insertionsort
 const int n=30001;
 const int m=30000;
 int i;int w;
  
 cout<<"|------快速排序與插入排序算法比較-----|"<<endl;
 cout<<"|-----------數(shù)據(jù)規(guī)模：30000-----------|"<<endl;
 cout<<"|---power by zhanjiantao(028054115)---|"<<endl;
 cout<<"---------------------------------------"<<endl;
 cout<<"running……"<<endl;
while(w)
{
 //INSERTIONSORT
    
 start=clock(); //start time
 
 int A[m];
 for(i=0;i<m;i++)
 A[i]=rand();

    Insertionsort(A,m);
 end=clock(); //finish time
 elapsed2=((float)end-start)/CLOCKS_PER_SEC;
 

//INSERTIONSORT

//QUICKSORT
 
 
 start=clock();//start time
    int R[n];
    for(i=1;i<=n;i++)
 R[i]=rand();
    Quicksort(R,1,n);
    end=clock(); //time finish
 elapsed1=((float)end-start)/CLOCKS_PER_SEC;
//QUICKSORT
 cout<<"選擇<3>驗(yàn)證insertionsort的正確性"<<endl;
 cout<<"選擇<2>驗(yàn)證quicksort的正確性"<<endl;
 cout<<"選擇<1>比較算法運(yùn)算時(shí)間"<<endl;
 cout<<"選擇<0>退出"<<endl;
 cin>>w;
 switch(w){
  case 3:for(i=0;i<m;i++)
   cout<<A[i]<<" ";
   break;
  case 2:for(i=1;i<n;i++)
   cout<<A[i]<<" ";
   break;
  case 1: cout<<"insertionsort的運(yùn)行時(shí)間:"<<elapsed2<<"s"<<endl;
          cout<<"quicksort的運(yùn)行時(shí)間:"<<elapsed1<<"s"<<endl;
   break;
  case 0: break;
  default: cout<<"錯(cuò)誤！請(qǐng)輸入正確的功能序號(hào)!"<<endl;
 }
 
}
}