#include <iostream> 
#include <stdlib.h> 
using namespace std; 
int count=0; 
void run(int *pData, int left, int right) 
{ 
int i,j; 
int middle, iTemp; 
int k; 
i = left; 
j = right; 
middle = pData[left+(rand()%(right-left))]; 
//middle= pData[(left+right)/2]; 
do{ 
   while((pData[i]<middle)&&(i<right)) 
    i++; 
   while((pData[j]>middle)&&(j>left)) 
    j--; 
   if(i<=j) 
   { 
    iTemp=pData[j]; 
    pData[j]=pData[i]; 
    pData[i]=iTemp; 
    i++; 
    j--; 
    count++; 
    
   } 
 
}while(i<j); 
cout<<"middle = "<<middle<<" i="<<i<<" j="<<j<<endl; 
    for(k=0; k<11; k++) 
     cout<<pData[k]<<" "; 
    cout<<endl; 
if(left<j) 
   run(pData,left,j); 
if(right>i) 
   run(pData,i,right); 
 
 
} 
void QuickSort(int *pData,int Count) 
{ 
run(pData, 0, Count-1); 
} 
void QuickSort2(int inta[],int low,int high) 
{ 
   int i=low,j=high; 
   int temp = inta[low]; 
   while(i<j) 
   { 
    while (i<j && temp<=inta[j]) 
     j--; 
    if(i<j) 
    { 
     inta[i]=inta[j]; 
        i++; 
    } 
    while(i<j && temp >=inta[i]) 
     i++; 
    if(i<j) 
    { 
     inta[j]=inta[i]; 
     j--; 
    } 
   } 
   inta[i]=temp; 
   int k=0; 
   for( k=0; k<11; k++) 
   cout<<inta[k]<<" "; 
cout<<endl; 
       if(i<high) QuickSort2(inta,i+1,high); 
          if(low<i) QuickSort2(inta,low,i-1); 
} 
void main() 
{ 
int data[]={10,9,8,7,11,6,5,4,3,2,1}; 
//int data[] = {1,2,3,4,5,6,7,8,9,10,11}; 
// QuickSort(data, 11); 
QuickSort2(data, 0, 10); 
cout<<"++++++++++++++++++++++++++++++++++++++\n"; 
for(int i=0; i<11; i++) 
   cout<<data[i]<<" "; 
cout<<endl; 
cout<<"count = "<<count; 
} 
 
/*******************************************************************************************************************************/ 
 
#include <iostream> 
#include <string> 
#include <vector> 
using namespace std; 
template <typename T> 
int pivotIndex(vector<T>& v, int first, int last) 
{ 
int mid, scanUp, scanDown; 
T pivot, temp; 
if (first == last) 
   return last; 
else if (first == last -1) 
   return first; 
else 
{ 
   mid = (last + first)/2; 
   pivot = v[mid]; 
 
   v[mid] = v[first]; 
   v[first] = pivot; 
 
   scanUp = first + 1; 
   scanDown = last - 1; 
   
   for (;;) 
   { 
    while (scanUp <= scanDown && v[scanUp] < pivot) 
     scanUp++; 
    while (pivot < v[scanDown]) 
     scanDown--; 
 
    if (scanUp >= scanDown) 
     break; 
    temp = v[scanUp]; 
    v[scanUp] = v[scanDown]; 
    v[scanDown] = temp; 
 
    scanUp++; 
    scanDown--; 
   } 
   v[first] = v[scanDown]; 
   v[scanDown] = pivot; 
   return scanDown; 
} 
} 
template <typename T> 
void quicksort(vector<T>& v, int first, int last) 
{ 
int pivotLoc; 
T temp; 
if (last - first <= 1) 
   return ; 
else if (last - first == 2) 
{ 
   if (v[last-1] < v[first]) 
   { 
    temp = v[last-1]; 
    v[last-1] = v[first]; 
    v[first] = temp; 
   } 
   return ; 
} 
else 
{ 
   pivotLoc = pivotIndex(v, first, last); 
   quicksort(v, first, pivotLoc); 
   quicksort(v, pivotLoc+1, last); 
} 
} 
int main() 
{ 
int intList[] = {2,56,23,12,599,1,3,67 
vector<int> v(intList, intList+sizeof(intList)/sizeof(int)); 
 
quicksort(v, 0, sizeof(intList)/sizeof(int)); 
for(int i=0; i< sizeof(intList)/sizeof(int); i++) 
   cout<<v[i]<<" "; 
cout<<endl; 
return 0; 
} 
 
/******************************************************************************/ 
 
template <typename T> 
void findK(vector<T>& v, int first, int last, int k) 
{ 
int index; 
index = pivotIndex(v, first, last);/* 中间值*/ 
if (index == k) 
   return; 
else if(k < index) 
   findk(v, first, index, k); 
else 
   findk(v, index+1, last, k); 
}